Amazon | OA 2019 | Two Sum - Unique Pairs

Posted on | Edited on | Views:

link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Java O(n)
class Solution {
    public static int uniquePairs(int[] nums, int target) {
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> seen = new HashSet<Integer>();
        int count = 0;
        for (int num : nums) {
            if (!seen.contains(num) && set.contains(target - num)) {
                count++;
                seen.add(target - num);
                seen.add(num);
            }
            set.add(num);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Java O(nlogn)
/*
public static int getUniquePairs(int[] nums, int target){
    Arrays.sort(nums);
    int i = 0;
    int j = nums.length-1;
    int ans = 0;
    while (i < j){
        int sum = nums[i]+ nums[j];
        if (sum < target){
            i++;
        } else if (sum > target){
            j--;
        } else {
            ans++;
            i++;
            j--;
            while (i < j && nums[i] == nums[i-1]){
                i++;
            }
            while (i < j && nums[j] == nums[j+1]){
                j--;
            }
        }
    }
    return ans;
}*/
0%