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 hereint 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 hereHashMap<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;}
}