Bài 1 Leetcode: Two Sum

Đề bài: 

Cho một mảng số nguyên nums và một số nguyên target, trả về các chỉ số của hai số sao cho tổng của chúng là target. Bạn có thể giả định rằng mỗi bộ dữ liệu đầu vào sẽ có đúng một lời giải và bạn không được sử dụng cùng một phần tử hai lần. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

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]

Ràng buộc:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Chỉ tồn tại một câu trả lời hợp lệ.

Giải thích thuật toán bằng C++

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex;

    for (int i = 0; i < nums.size(); ++i) {
      if (const auto it = numToIndex.find(target - nums[i]);
          it != numToIndex.cend())
        return {it->second, i};
      numToIndex[nums[i]] = i;
    }

    throw;
  }
};

Đây là một giải pháp trong ngôn ngữ lập trình C++ để tìm hai số trong một mảng số nguyên (nums) sao cho tổng của chúng là một giá trị nhất định (target).

Thuật toán được sử dụng là một phương pháp duyệt mảng và sử dụng một bảng băm (unordered_map) để lưu trữ các số đã được xem xét và chỉ số tương ứng của chúng.

Cụ thể, thuật toán hoạt động như sau:

1. Khởi tạo một unordered_map có tên numToIndex để lưu trữ các số đã được xem xét và chỉ số tương ứng của chúng.
2. Duyệt qua mảng nums từ đầu đến cuối bằng vòng lặp for, với biến đếm i từ 0 đến kích thước của mảng nums.
3. Trong mỗi lần lặp, kiểm tra xem phần tử (target – nums[i]) có tồn tại trong unordered_map numToIndex hay không. Để làm điều này, sử dụng hàm find() của unordered_map và so sánh với con trỏ end() của unordered_map. Nếu tìm thấy, có nghĩa là đã tìm thấy cặp số thỏa mãn yêu cầu và ta trả về một vector chứa chỉ số của hai số đó (it->second và i).
4. Nếu không tìm thấy cặp số thỏa mãn yêu cầu, ta tiếp tục lưu trữ phần tử nums[i] vào unordered_map numToIndex với chỉ số là i.
5. Nếu không có cặp số nào thỏa mãn yêu cầu, ta ném một ngoại lệ (throw).

Tổng quát, thuật toán này sử dụng bảng băm để lưu trữ thông tin về các số đã được xem xét và chỉ số tương ứng của chúng. Khi duyệt qua mảng, ta kiểm tra xem phần tử cần tìm (target – nums[i]) đã tồn tại trong bảng băm hay chưa. Nếu đã tồn tại, ta trả về kết quả. Nếu không, ta tiếp tục lưu trữ phần tử hiện tại vào bảng băm. Điều này giúp giảm đáng kể độ phức tạp thời gian so với phương pháp duyệt tất cả các cặp số có thể.

Giải thích thuật toán bằng Java

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      if (numToIndex.containsKey(target - nums[i]))
        return new int[] {numToIndex.get(target - nums[i]), i};
      numToIndex.put(nums[i], i);
    }

    throw new IllegalArgumentException();
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    numToIndex = {}

    for i, num in enumerate(nums):
      if target - num in numToIndex:
        return numToIndex[target - num], i
      numToIndex[num] = i