用Java解决三数之和的问题
时间: 2024-05-03 10:16:23 浏览: 7
三数之和问题是指在一个数组中找到所有满足三个数相加等于0的不重复的三元组。以下是Java代码实现:
```java
import java.util.*;
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {
result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++; hi--;
} else if (nums[lo] + nums[hi] < sum) {
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
lo++;
} else {
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
hi--;
}
}
}
}
return result;
}
}
```
这里使用了双指针法来优化时间复杂度,并且排除了重复元素。时间复杂度为O(n^2)。