Cùng giải leetcode! Bài 1. Two Sum

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/two-sum/

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à một số nguyên target. Hãy tìm hai phần tử mà tổng của chúng chính bằng target, trả về kết quả là vị trí index của chúng trong mảng nums.
Mỗi phần tử trong mảng chỉ được sử dụng một lần trong phép tính tổng.
Kết quả trả về dưới dạng mảng, sắp xếp theo thứ tự bất kì.

Điều kiện:

• 2 <= nums.length <= 10^4.
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9.

Ví dụ 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Ví dụ 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Ví dụ 3:

Input: nums = [3,3], target = 6
Output: [0,1]

3. Phân tích

Với bài này chúng ta sẽ có hai cách giải:

• Cách đầu tiên cũng là cách thông thường, chúng ta sẽ sử dụng thuật toán Brute Force (thuật toán vét cạn) để kiểm tra tổng mỗi cặp phần tử trong mảng nums xem chúng có bằng target không? Nếu bằng nhau thì trả về mảng chứa hai ví trị index của chúng.
• Cách thứ hai thì chúng ta sẽ dùng đến cấu trúc dữ liệu HashSet. Vì chúng ta cần index của hai phần tử trong mảng nums, nên ta sẽ lưu một con trỏ ở ngoài vòng lặp tên i. Sau đó duyệt qua mảng nums với con trỏ i ở trên, với mỗi phần tử chúng ta kiểm tra xem ở trong set đã tồn tại phần tử nào mà target - nums[i] chưa? Nếu chưa thì ta thêm phần tử hiện tại nums[i] vào, còn nếu đã tồn tại phần tử thỏa mãn target - nums[i] thì ta dừng vòng lặp luôn. Khi này ta biết chắc rằng hai phần tử mà tổng của chúng bằng target sẽ nằm từ index = 0 đến index = i. Ta chỉ duyệt thêm một lần nữa qua mảng nums, nhưng khác là chúng ta sẽ lặp một mảng với kích thước nhỏ hơn kích thước ban đầu rất nhiều.

4. Code chạy bằng cơm

4.1. Thuật toán Brute Force

Hãy chạy code với ví dụ nums = [2,7,11,15], target = 18, vì chúng ta chỉ được dùng mỗi phần tử một lần cho phép tính tổng, nên ta cần có hai con trỏ i và j với j > i:

Chúng ta cứ tuần tự kiểm tra từng cặp phần tử rồi so sánh chúng với target:

Tại đây thì ta thấy nums[i] + nums[j] = 18 cũng chính là target:

Vậy ta có kết quả chính là mảng chứa hai index i và j:

4.2. Sử dụng HashSet

Đầu tiên chúng ta cần một con trỏ i lưu ở ngoài vòng lặp, lí do là nếu con trỏ i được khởi tạo trong vòng lặp, sau khi lặp xong nó sẽ biến mất, mà ta thì cần giá trị cuối cùng của i.
Bây giờ ta vẫn duyệt qua mảng nums với con trỏ i, với mỗi phần tử, ta sẽ kiểm tra xem target trừ đi phần tử đó được bao nhiêu, thì cái số đó có nằm trong set hay chưa? Nếu chưa thì thêm nums[i] nếu rồi thì dừng vòng lặp.
Hãy thử với ví dụ như ở trên:
Tại i = 0, ta thấy target - nums[0] = 16, kiểm tra thì không thấy 16 không có ở trong set, vậy nên ta sẽ thêm nums[0] = 2 vào trong set:

Tiếp theo, kiểm tra target - nums[1] = 11, không thấy 11 ở trong set nên ta thêm 7 vào:

Tại i = 2, ta thấy target - nums[2] = 7, và trong set đã có 7 rồi, vậy nên ta dừng vòng lặp tại đây với i = 2:

Lúc này ta biết chắc chắn rằng trong khoảng từ 0 tới i = 2 có chứa hai số mà tổng của chúng bằng target. Vậy nên ta chỉ cần duyệt từ 0 tới i mà thôi:

Giờ ta sẽ tìm số còn lại bằng cách lấy target trừ đi nums[i], rồi trả về kết quả là xong!

5. Code bằng máy

5.1. Thuật toán Brute Force

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
       int[] res = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                 if (nums[i] + nums[j] == target){
                  res[0] = i;
                  res[1] = j;
                }
            }
        }
   
        return res;
    }
}

5.2. Sử dụng HashSet

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Set<Integer> setInt = new HashSet<>();
        int i;
        int[] arr = new int[2];
   
        for (i = 0; i < nums.length; i++) {
            if (setInt.contains(target - nums[i])) {
                break;
            }
            setInt.add(nums[i]);
        }
   
        for (int j = 0; j < i; j++) {
            if(target - nums[i] == nums[j]){
                arr[0] = i;
                arr[1] = j;
            }
        }
   
        return arr;
    }
}

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!!!