Cho một mảng số nguyên n phần tử, và số nguyên sum cho trước. Tìm tất cả các cặp số có tổng bằng sum.
Ví dụ:
Input: arr[] = {1, 4, 6, 2, 3, 0, -1}, sum = 5
Output: {2, 3}, (6, -1), {4, 1}
Cách đơn giản nhất là dùng 2 vòng lặp để tìm ra tất cả các giá trị tổng và so sánh. =) cách này dễ các bạn tự làm nghen. Cách này tiêu tốn O(n^2).
Mình mong muốn O(n), cho nên mình sẽ nghĩ một xíu
Đầu tiên mình sẽ chuyển array qua Map với key là giá trị của phần tử trong mảng, value là số lần xuất hiện.
Sau đó duyệt mảng và kiểm tra cặp số arr[i] và sum – arr[i] có chứa trong mảng không? nếu có thì có cặp số thoả sum và sum – arr[i] sau đó trừ đi 1 vào số lần xuất hiện của cả hai trong Map
public static void main(String[] args) {
int[] arr = {1, 4, 6, 2, 3, 0, -1};
int sum = 5;
Map<Integer, Integer> map = new HashMap<>();
for (int value : arr) {
if (map.containsKey(value)) {
map.put(value, map.get(value) + 1);
} else {
map.put(value, 1);
}
}
for (int i=0; i< arr.length; i++)
{
if(map.get(sum-arr[i]) != null && map.get(sum - arr[i]) >= 1 && map.get(arr[i]) >= 1) {
System.out.println(arr[i] + " - " + (sum - arr[i]));
map.put(sum - arr[i], map.get(sum - arr[i]) - 1);
map.put(arr[i], map.get(arr[i]) - 1);
}
}
}
Output:
1 – 4
6 – -1
2 – 3
Độ phức tạp O(n)