Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Cho một mảng gồm các số nguyên nums và một số nguyên target, hãy trả về chỉ số của hai số sao cho tổng của chúng bằng target. Bạn có thể cho rằng mỗi đầu vào sẽ có chính xác một giải pháp và bạn không thể sử dụng cùng một phần tử hai lần.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]Chúng ta có thể sử dụng HashMap để lưu trữ từng phần tử của mảng dưới dạng key và chỉ mục của nó dưới dạng value. Sau đó, chúng ta lặp qua mảng và kiểm tra xem phần bù của phần tử hiện tại (tức là target trừ đi phần tử hiện tại) đã có trong HashMap chưa. Nếu có, thì chúng ta đã tìm thấy một cặp chỉ số bổ sung cho mục tiêu và chúng ta trả về các chỉ số đó. Mặt khác, chúng ta thêm phần tử hiện tại và chỉ mục của nó vào HashMap và tiếp tục đến phần tử tiếp theo.
Nếu chúng ta đến cuối vòng lặp mà không tìm ra giải pháp, chúng ta sẽ đưa ra một ngoại lệ để chỉ ra rằng không có cặp chỉ số hợp lệ nào.
Lưu ý rằng độ phức tạp về thời gian của giải pháp này là O(n), vì chúng ta chỉ lặp qua mảng một lần. Độ phức tạp của không gian cũng là O(n), vì chúng ta cần lưu trữ từng phần tử trong HashMap.
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
Trên đây là ví dụ hướng dẫn giải bài toán Two Sum Leetcode dành cho các bạn tham khảo.
Cảm ơn các bạn đã ghé thăm. Chúc các bạn thành công!
