Cho một mảng arr đựợc sắp xếp tăng dần, có số lượng phần tử là n. Tìm cặp số (arr[i] và arr[j]) sao cho tổng arr[i] + arr[j] = sum với sum là số cho trước. Nếu có cặp số arr[i], arr[j] thoả thì trả về true ngược lại false.
Cách 1: Loop
public class Main {
public static boolean isPairSumSimple(int[] arr, int n, int sum) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == sum)
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {1, 4, 7, 4, 7, 3, 7, 3, 8, 3, 2, 5, 7};
System.out.println(isPairSumSimple(arr, arr.length, 10));
}
}
Output: true
Độ phức tạp: O(n2)
Cách 2: Apply sorted
Để ý rằng đề bài cho chúng ta mảng tăng dần. Nếu mình đặt l = 0, r = n – 1, thì nếu arr[i] + arr[j] > sum thì sao nào? Có 2 trường hợp:
- l = l + 1 =? tổng tăng(mảng tăng dần => arr[l] <= arr[l + 1])
- r = r – 1 =? tổng giảm(mảng tăng dần => arr[r] >= arr[r – 1)
Vậy chúng ta thấy rằng tại thời điểm chúng ta đang xét arr[l] + arr[r] > sum, chúng ta chỉ còn cách giảm tổng xuống mới có thể thoả arr[l] + arr[r] = sum => giảm r. Trường hợp ngược lại thì tăng l.
public class Main {
public static boolean isPairSum(int[] arr, int n, int sum) {
int l = 0, r = n - 1;
while (l < r) {
if (arr[l] + arr[r] == sum)
return true;
else if (arr[l] + arr[sum] > sum)
r--;
else l++;
}
return false;
}
public static void main(String[] args) {
int[] arr = {1, 4, 7, 4, 7, 3, 7, 3, 8, 3, 2, 5, 7};
System.out.println(isPairSum(arr, arr.length, 10));
}
}
Output: true
Độ phức tạp: O(n)
Link source: source
Nguồn tham khảo: https://www.geeksforgeeks.org/two-pointers-technique/