描述
給一整數(shù)數(shù)組, 找到數(shù)組中有多少組 不同的元素對 有相同的和, 且和為給出的 target 值, 返回對數(shù).
樣例
給一數(shù)組 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++;
/* 此處應(yīng)注意while和if區(qū)別:
* 只要滿足判斷條件，while可重復(fù)執(zhí)行多次，而if只執(zhí)行一次得糜，
* 此處if執(zhí)行一次會導(dǎo)致出現(xiàn)重復(fù)解
* 下面兩個while判斷時加left < right是要防止在
* left < right且left和right相鄰時因?yàn)樯厦娴膌eft++和right--
* 已經(jīng)不滿足left < right的執(zhí)行條件依然繼續(xù)執(zhí)行下面的語句
* 從而導(dǎo)致結(jié)果出問題
*/
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;
}
}
