Cùng giải leetcode! Bài 219. Contains Duplicate II

Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/contains-duplicate-ii/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho mảng số nguyên nums và số nguyên k. Trả về kết quả là true nếu có hai con trỏ khác nhau i và j thỏa mãn nums[i] == nums[j] và abs(i - j) <= k.
Điều kiện:

• 1 <= nums.length <= 10^5.
• -10^9 <= nums[i] <= 10^9.
• 0 <= k <= 105.

Bài toán minh họa 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Bài toán minh họa 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Bài toán minh họa 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

3. Phân tích

Lại là một bài tìm số trùng lặp trong mảng, nhưng phiên bản này khó hơn một chút. Còn phiên bản dễ hơn thì tôi đã có bài viết tại đây.
Bài này chúng ta vẫn có thể sử dụng thuật toán Brute Force (thuật toán vét cạn) để xử lý, tuy nhiên như tôi đã nói ở bài trên, độ phức tạp sẽ lên đến O(n^2) và điều này không tốt một chút nào, nên chúng ta sẽ không giải bằng kỹ thuật này.
Ố kề. Bài này nếu như chỉ tìm ra cặp số giống nhau như bài 217 thì không khó. Vấn đề ở đây là nó phải thỏa mãn điều kiện nữa là khoảng cách giữa hai con trỏ i và j phải nhỏ hơn hoặc bằng số nguyên k.
Như ở ví dụ 1, chúng ta có hai số giống nhau là 1 và chúng ở vị trí 0 và 3, mà |0 - 3| = 3 cũng chính bằng k, nên kết quả trả về true:

Tuy nhiên ở ví dụ 3, mặc dù cũng có cặp số giống nhau, nhưng lại không thỏa mãn điều kiện, nên kết quả trả về false:

Vậy nên, ở bài này chúng ta sẽ sử dụng cấu trúc dữ liệu HashMap để giải quyết bài toán. Với key chính là phần tử trong nums, còn value là vị trí hiện tại của phần tử đó trong mảng. Tại sao lại là vị trí hiện tại? Nếu như phần tử đó chưa có trong map, ta sẽ thêm nó vào; còn nếu như phần tử đó có rồi, ta sẽ phải đồng thời kiểm tra xem hiệu giữa index hiện tại và index đã được lưu trong value có nhỏ hơn hoặc bằng k hay không? Nếu có thì trả về true còn không thì false.

4. Code bằng cơm

Đầu tiên chúng ta cần tạo mới một HashMap.

Tiếp theo chúng ta sẽ một vòng lặp for để duyệt qua mảng nums. Khi này chúng ta sẽ làm hai công việc một lúc, ấy là kiểm tra xem nếu phần tử đó có trong map hay chưa? Nếu chưa có thì ta thêm vào map, còn chưa có thì ta sẽ phải kiểm tra tiếp. Ta kiểm tra xem, với cái phần tử này đã có trong map rồi, thì cái index đã lưu trong value ấy với cái index hiện tại trừ đi nhau liệu có nhỏ hơn hoặc bằng k hay không?

Done! Chúng ta tới bước tiếp theo thôi!

5. Code bằng máy

Code của chúng ta sẽ như sau:

 public boolean containsNearbyDuplicate(int[] nums, int k) {

     Map<Integer, Integer> map = new HashMap<>();
     for (int i = 0; i < nums.length; i++) {
         if (map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k) {
             return true;
         }
         map.put(nums[i], i);
     }

     return false;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!