描述
给一整数数组, 找到数组中有多少组 不同的元素对 有相同的和, 且和为给出的 target 值, 返回对数.
样例
给一数组 nums = [1,1,2,45,46,46], target = 47, 返回 2
1 + 46 = 47
2 + 45 = 47
代码
public class Solution {
/*
* @param nums: an array of integer
* @param target: An integer
* @return: An integer
*/
public int twoSum6(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return 0;
}
int left = 0, right = numbers.length - 1;
int count = 0;
Arrays.sort(numbers);
while (left < right) {
if (numbers[left] + numbers[right] == target) {
left++;
right--;
count++;
/* 此处应注意while和if区别:
* 只要满足判断条件，while可重复执行多次，而if只执行一次，
* 此处if执行一次会导致出现重复解
* 下面两个while判断时加left < right是要防止在
* left < right且left和right相邻时因为上面的left++和right--
* 已经不满足left < right的执行条件依然继续执行下面的语句
* 从而导致结果出问题
*/
while (left < right && numbers[left - 1] == numbers[left]) {
left++;
}
while (left < right && numbers[right + 1] == numbers[right]) {
right--;
}
} else if (numbers[left] + numbers[right] > target) {
right--;
} else {
left++;
}
}
return count;
}
}
