题目来自：https://leetcode-cn.com/problems/3sum/description/
给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：
这道题挺简单的。
首先要明白一个三元组关系 a>=b>=i 所以首先就是把数组按从小到大重新排序。
了解 二元组的和等于给定值sum 情况的话，就知道数组排序后，用两个指向数组的指针，一个从前向后扫描，一个从后向前扫描，记为first和last；
当 first + last == sum 则找到了一对二元组，它们的和等于sum；
如果 first + last < sum 则再去取左边更大的值，所以 first++；
如果 first + last > sum 则再去取右边更小的值，所以 last-- 。
同样，三元组的情况，先将数组从小到大排序，然后固定一个元素 chooiseNum ，再去寻找一个二元组的和为sum + chooiseNum == 0 ，这样就将三元组的问题，转换成了二元组的问题。
private static int[] num = {-1, 0, 1, 2, -1, -4};
public static void main(String[] args) {
sortNums(num);
System.out.print("排序后的数组：");
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
System.out.println(" ");
solutionThirdNum(num);
}
public static void solutionThirdNum(int[] nums) {
for (int i = 0; i< nums.length; i++) {
int chooiseNum = nums[i];
int left = 0, right = nums.length-1;
while(left < right) {
int sum = nums[left] + nums[right];
if(i == left || i == right) {
break;
}
if(chooiseNum + sum < 0) {
left++;
continue;
}
if(chooiseNum + sum > 0) {
right--;
continue;
}
if(chooiseNum + sum == 0) {
if(left >= i ) {
System.out.println(" [ " + nums[i] + ","+ nums[left] +"," + nums[right] + " ]");
}
if(left < i && i < right) {
System.out.println(" [ " + nums[left] + ","+ nums[i] +"," + nums[right] + " ]");
}
if(right <= i) {
System.out.println(" [ " + nums[left] + ","+ nums[right] +"," + nums[i] + " ]");
}
break;
}
}
}
}
// 冒泡排序--> 从小到大
public static int[] sortNums(int[] sortNum) {
for (int i = 0; i < sortNum.length - 1; i++) {
for (int j = 0; j < sortNum.length - i - 1; j++) {
if (sortNum[j] > sortNum[j + 1]) {
int temp = sortNum[j];
sortNum[j] = sortNum[j + 1];
sortNum[j + 1] = temp;
}
}
}
return sortNum;
}
网友评论