1.两数之和
题目链接
题目描述
解题思路
1.暴力法
双重for循环,时间复杂度O(n*n)
2.排序+双指针
3.哈希表
AC代码
//利用哈希表，一步到位，时间复杂度O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
2.三数之和
题目链接
题目描述
解题思路
1.最朴素的解法：暴力，三重for循环，可能会超时
2.排序+双指针
注意本题不适合采用哈希表，如果采用哈希表，需要去重操作，需要注意更多的细节。
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向nums[i]后面的两端，数字分别为 nums[L]和nums[R]，计算三个数的和 sum，判断是否满足为 0，满足则添加进结果集
-
如果nums[i]大于0，则三数之和必然无法等于0，结束循环
-
如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
-
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
-
当 sum == 0 时，nums[R] == nums[R-1]则会导致结果重复，应该跳过，R−−
时间复杂度：O(n^2)
AC代码
//利用set集合去重，刚好卡着时间过，去重是可以通过手写代码优化，不需要利用set集合。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
Set<LinkedList<Integer>> st = new HashSet<>();
Arrays.sort(nums);
int index = 0;
if(nums.length==0) return ans;
while(true){
if(nums[index] > 0 || index > nums.length - 3) break;
int l = index+1;
int r = nums.length-1;
while(l < r){
if(nums[index]+nums[l]+nums[r] == 0){
LinkedList<Integer> temp = new LinkedList<>();
temp.add(nums[index]);
temp.add(nums[l]);
temp.add(nums[r]);
if(st.add(temp)) ans.add(temp);
l++;
if(nums[l] == nums[l-1]) l++;
}else if(nums[index]+nums[l]+nums[r] < 0){
l++;
if(nums[l] == nums[l-1]) l++;
}
else if(nums[index]+nums[l]+nums[r] > 0){
r--;
if(nums[r] == nums[r+1]) r--;
}
}
index++;
}
return ans;
}
}
//优化后的代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
Arrays.sort(nums);
int index = 0;
if(nums.length==0) return ans;
while(true){
if(index > nums.length - 3 || nums[index] > 0 ) break;
int l = index+1;
int r = nums.length-1;
while(l < r){
if(nums[index]+nums[l]+nums[r] == 0){
LinkedList<Integer> temp = new LinkedList<>();
temp.add(nums[index]);
temp.add(nums[l]);
temp.add(nums[r]);
ans.add(temp);
l++;
//去重
while(l<nums.length && nums[l] == nums[l-1]) l++;
}else if(nums[index]+nums[l]+nums[r] < 0){
l++;
//去重
while(l < nums.length && nums[l] == nums[l-1]) l++;
}
else if(nums[index]+nums[l]+nums[r] > 0){
r--;
//去重
while(r > -1 && nums[r] == nums[r+1]) r--;
}
}
index++;
//去重
while(index < nums.length && nums[index] == nums[index-1]) index++;
}
return ans;
}
}
3.四数之和
题目链接
题目描述
解题思路
1.暴力，四重for循环
2.排序+双指针
AC代码
//暴力法，四重for循环
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new LinkedList<>();
Set<LinkedList> s = new HashSet<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
for(int j = i+1; j < nums.length; j++){
for(int k = j + 1; k < nums.length; k++){
for(int g = k + 1; g < nums.length; g++){
if(nums[i]+nums[j]+nums[k]+nums[g]==target){
LinkedList temp = new LinkedList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
temp.add(nums[g]);
if(s.add(temp)) ans.add(temp);
}
}
}
}
}
return ans;
}
}
//排序+双指针
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new LinkedList<>();
Set<List<Integer>> hashset = new HashSet<>();
Arrays.sort(nums);
if(nums.length < 4) return ans;
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
int l = j + 1;
int r = nums.length-1;
while(l < r){
if(nums[i]+nums[j]+nums[l]+nums[r] == target){
LinkedList temp = new LinkedList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[l]);
temp.add(nums[r]);
if(hashset.add(temp)) ans.add(temp);
l++;
}else if(nums[i]+nums[j]+nums[l]+nums[r] < target){
l++;
}else if(nums[i]+nums[j]+nums[l]+nums[r] > target){
r--;
}
}
}
}
return ans;
}
}
n数之和
在三数和四数之和中，我们利用排序+双指针都直接把暴力方法的时间复杂度降了一级，除了二数之和外，n数之和都可以采用排序+双指针的解决方法。