LintCode 587 Two Sum - Unique pairs

思路1

排序+雙指針。指針移動的過程中，遇到了相同的元素就直接跳過。

時間複雜度O(nlogn)

空間複雜度O(1)

代碼1

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: An integer
     * @return: An integer
     */
    public int twoSum6(int[] nums, int target) {
        // write your code here
        int result = 0;
        if (nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                result++;
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}
           

思路2

不排序，使用hashmap來做。由于target确定後，再确定一個元素，另一個元素也定了，是以利用hashmap來記錄某個元素是否被使用，進而達到去重的目的（key：元素; value：bool，是否被使用）。

時間複雜度O(n)

空間複雜度O(n)

代碼2

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: An integer
     * @return: An integer
     */
    public int twoSum6(int[] nums, int target) {
        // write your code here
        HashMap<Integer, Boolean> map = new HashMap<>();
        int count = 0;
        
        for (int n : nums) {
            int rest = target - n;
            if (map.containsKey(rest)) {
                if (!map.get(rest)) {
                    map.put(n, true);
                    map.put(rest, true);
                    count++;
                }
            } else {
                map.put(n, false);
            }
        }
        
        return count;
    }
}