leetcode15.三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
真难啊，想了半个小时还是没啥思路，看的题解，这一篇比较好。
画解算法：15.三数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int left=0,right=nums.length-1;
ArrayList<List<Integer>>list=new ArrayList<>();
for(int i=0;i<nums.length;i++) {
if(nums[i]>0)break;
if(i>0&&nums[i]==nums[i-1])continue;
left=i+1;
right=nums.length-1;
while(left<right) {
int sum=nums[i]+nums[left]+nums[right];
if(sum==0) {
ArrayList<Integer>tmp=new ArrayList<>();
tmp.add(nums[i]);
tmp.add(nums[left]);
tmp.add(nums[right]);
list.add(tmp);
while(left<right&&nums[left]==nums[left+1])left++;
while(left<right&&nums[right]==nums[right-1])right--;
left++;
right--;
}else if(sum>0) {
right--;
}else {
left++;
}
}
}
return list;
}
|
leetcode 10/100