题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意： 答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
总结
剪枝优化
Sample & Demo Code
class Solution {
public List
<List
<Integer>> fourSum(int[] nums
, int target
) {
List
<List
<Integer>> result
= new ArrayList<>();
if (nums
== null
|| nums
.length
== 0) return result
;
Arrays
.sort(nums
);
for (int k
= 0; k
< nums
.length
; k
++) {
if (k
> 0 && nums
[k
] == nums
[k
-1]) continue;
if(nums
[k
] + 3*nums
[nums
.length
-1]<target
)continue;
if(nums
[k
] > target
/4) break;
int temp
= target
- nums
[k
];
for(int m
= k
+1; m
< nums
.length
; m
++) {
if((m
> k
+1 && nums
[m
] == nums
[m
-1])) continue;
if(nums
[m
] > (target
-nums
[k
])/3) break;
int sum
= temp
- nums
[m
];
int i
= m
+ 1;
int j
= nums
.length
- 1;
while (i
< j
) {
if (nums
[i
] + nums
[j
] == sum
) {
List
<Integer> r
= new ArrayList<>();
r
.add(nums
[k
]);
r
.add(nums
[m
]);
r
.add(nums
[i
]);
r
.add(nums
[j
]);
result
.add(r
);
while (i
< j
&& nums
[i
] == nums
[i
+ 1]) ++i
;
while (i
< j
&& nums
[j
] == nums
[j
- 1]) --j
;
++i
;
--j
;
} else if (nums
[i
] + nums
[j
] < sum
) ++i
;
else --j
;
}
}
}
return result
;
}
}
