Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.
Example
Given nums = [1,1,2,45,46,46], target = 47
return 2
1 + 46 = 47
2 + 45 = 47
思路
老样子,先排序。
一个从左,一个从右,往当中走。
如果加起来等于target,那么左边往右走到不是左边这个数的地方,右边往左走到不是右边这个数字的地方。
然后接着比。
Code
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 if (nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int count = 0; int left = 0; int right = nums.length - 1; while (left < right) { if (nums[left] + nums[right] < target) { left++; } else if (nums[left] + nums[right] > target) { right--; } else { count++; left++; right--; while (left < right && nums[left] == nums[left - 1]) { left++; } while (left < right && nums[right] == nums[right + 1]) { right--; } } } return count; } }