package com.wjk.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author : RobertWei
* time: 2021/9/9 17:06
* description:三数之和答案
*/
public class Answer {
public static void main(String[] args) {
int[] nums = {0, 2, 5, 3, -2, -3};
List<List<Integer>> threeSum = threeSum(nums);
System.out.println("threeSum = " + threeSum);
}
public static List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length <= 2) {
return ans;
}
// O(nlogn)
Arrays.sort(nums);
// O(n^2)
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
// 第一个数大于 0，后面的数都比它大，肯定不成立了
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 去掉重复情况
}
int target = -nums[i];
int left = i + 1, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 现在要增加 left，减小 right，但是不能重复，
// 比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
// 首先无论如何先要进行加减操作
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[left] + nums[right] < target) {
left++;
} else {
// nums[left] + nums[right] > target
right--;
}
}
}
return ans;
}
}
java算法题 : 数组相关问题
需积分: 5 49 浏览量
2024-03-14
08:43:07
上传
评论
收藏 28KB RAR 举报
algorithm-learning-record-master.rar （44个子文件） 
algorithm-learning-record-master sortList src com wjk test 
Answer.java 2KB Demo.java 676B 链表排序 问题描述 476B sortList.iml 423B threeSum src com wjk test DemoTest.java 2KB Answer.java 2KB 解题思路 5KB 三数之和 问题描述 652B threeSum.iml 423B sortColors sortColors.iml 423B src com wjk test Demo.java 2KB 解题思路 3KB 颜色分类 问题描述 902B palindromeList src com wjk test Answer.java 2KB Demo.java 973B GodMethod.java 843B 回文链表 问题描述 501B palindromeList.iml 423B .idea vcs.xml 180B misc.xml 397B inspectionProfiles Project_Default.xml 1KB modules.xml 1KB .gitignore 244B encodings.xml 238B Array&DoublePointer.iml 423B circularList circularList.iml 423B src com wjk test Demo.java 1KB 环形链表 问题描述 1KB removeNthFromEnd src com wjk test Answer.java 590B UseStack.java 676B Demo.java 1KB removeNthFromEnd.iml 423B 从后删除链表 问题描述 238B 解题思路 1KB minCoverageSubstring 最小覆盖子串 问题描述 1KB src com wjk test Demo.java 222B Solution.java 2KB 解题思路 573B minCoverageSubstring.iml 423B moveZero src com wjk test BiggestAnswer.java 380B Answer.java 553B Demo.java 726B moveZero.iml 423B 移动零 问题描述 289B资源评论
