题目解析

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.

分析步骤

1、条件给出子元素三个和为0
2、限制和前置条件, 非重复数组
3、思路:最直接的思路未尝不好, 限制仅为3数

代码演示:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
public class A15Sum3 {
/**
* 直接处理方式
*
* @param nums
* @param target
* @return
*/
public static List<List<Integer>> sum3(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length < 3) { // 初始条件检查
return result;
}
Arrays.sort(nums); // 排好序
for (int i = 0; i < nums.length; i++) {
int start = i + 1, end = nums.length - 1;
int tmp = target - nums[i];
if (i > 0 && nums[i] == nums[i - 1]) { // 相等元素 继续下一个
continue;
}
while (start < end) {
if (tmp < nums[start] + nums[end]) {
end--;
} else if (tmp > nums[start] + nums[end]) {
start++;
} else {
List<Integer> tmp2 = new ArrayList<Integer>();
tmp2.add(nums[i]);
tmp2.add(nums[start]);
tmp2.add(nums[end]);
start++;
end--;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
while (end > start && nums[end] == nums[end + 1]) {
end--;
}
result.add(tmp2);
}
}
}
return result;
}
/**
* N数和或者和靠近处理模式
*
* @param nums
* @param target
* @return
*/
public static List<List<Integer>> sum3New(int[] nums, int target) {
Map<List<Integer>, List<Integer>> result = new HashMap<>();
Arrays.sort(nums);
sum3Backtracking(result, new ArrayList<Integer>(), nums, target, 0);
return new ArrayList<>(result.values());
}
/**
* backtracking 来处理
*
* @param result
* @param item
* @param nums
* @param remain
* @param start
*/
public static void sum3Backtracking(Map<List<Integer>, List<Integer>> result, List<Integer> item, int[] nums, int remain, int start) {
if (nums.length> 0 && remain < minArraySum(nums)) {
return;
} else if (remain == 0 && item.size() == 3) { // 符合结果值
result.put(new ArrayList<>(item), new ArrayList<>(item)); // 按照题目要求,简单用hashmap去重复数组
} else {
for (int i = start; i < nums.length; i++) {
item.add(nums[i]);//* ① 添加当前元素
sum3Backtracking(result, item, nums, remain - nums[i], i + 1); //* ② 之前的目标值为remain-nums[i]
item.remove(item.size() - 1); // * ③ 回退元素
}
}
}
/**
* 计算出当前最小值, 退出递归的条件,减少递归次数
* @param nums
* @return
*/
private static int minArraySum(int[] nums) {
int start = 0;
if (start >= nums.length) {
return Integer.MAX_VALUE;
}
if (nums[start] >= 0) {
return nums[start];
} else {
int min = 0;
for (int i = start; i < nums.length; i++) {
if (nums[i] < 0 && i < 4) {
min += nums[i];
}
}
return min;
}
}
public static void main(String[] args) {
System.out.println(sum3(new int[]{0, 0, 0, 0, 0, 0}, 0));
System.out.println(sum3New(new int[]{0, 0, 0, 0, 0, 0}, 0));
//
System.out.println(sum3(new int[]{-2, -1, 0, 1, 2, 3}, 0));
System.out.println(sum3New(new int[]{-2, -1, 0, 1, 2, 3}, 0));
}
}

代码文件:
A15Sum3.java

总结

  • 首先相当的类似回溯处理, 需要解决的是重复数组结果问题
  • 直接处理方式, 避免了重复检查, 当限制进位3数和,可以直接考虑
  • 延伸问题: N数和 或者 N数和接近,这类仅是结束条件变更的扩展

版权声明:本文为博主原创文章,未经允许不得转载。