看了b站up主 英雄哪里出来 做的算法视频,感觉挺有意思的,才想着做一做这些题,不得不说脑子确实不行,看了题解很久才想出来,过了一段时间不写又忘了怎么写的。。。
两数之和 (leetocde-1)
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 比如:nums = [2,7,11,15], target = 9,那么返回[0,1]或者[1,0]都可以。
遍历两回:
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length;j++){
if(nums[i]+nums[j]==target && i!=j){
res[0] = i;
res[1] = j;
}
}
}
return res;
}
虽然能够通过,但是太复杂,考虑只遍历一次
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(!map.containsKey(nums[i])){
map.put(target-nums[i],i);
}else{
res[0] = i;
res[1] = map.get(nums[i]);
break;
}
}
return res;
}
使用Map来存储,如果map中不存在数组中的当前值,那么把对应的target-nums[i]放到map中,下标i为value,等到遍历数组,发现当前值已经在map中了,那么说明此时已经找到了一组解,取出来就行了,此时结束循环。
三数之和(leetocde-15)
用二分法,先对数组进行排序,对数组进行遍历,定义left=i+1、right=nums.length-1对于当前的nums[i]和下一个数nums[left]和最后一个数nums[right],求和,如果和大于0,那么right--;小于0,left++;等于0,则把三个数组成的数组放进结果数组里。然后left++、right--。需要注意遍历的范围为 <n-2 ,因为遍历时候要保证当前nums[i]后面有两个数.
如果用list等集合来判断当前的解是否存在于结果数组中,很容易出现超时或者所花时间太多,因为集合的contains方法也会对集合进行遍历。
那么可以在每次拿到一组解后,继续对left和right进行加减,每次加减完,都要判断加减完后的num[left]和nums[right]与原来的值是否相同,相同则继续执行加减操作。因为若相同,那么就算有另一组解,也是已经找到的解。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int n=nums.length;
int left=0,right=n-1;
for(int i=0;i<n-2;i++){
if(i>0 && nums[i]==nums[i-1]){
continue;
}
if(nums[i]>0){
break;
}
left = i+1;
right = n-1;
while(left<right){
int k = nums[i]+nums[left]+nums[right];
if(k==0){
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
while(left<right && nums[left]==nums[left-1]) {
left++;
}
right--;
while(left<right && nums[right]==nums[right+1]) {
right--;
}
}else if(k<0){
left++;
}else{
right--;
}
}
}
return res;
}
四数之和 (leetocde-18)
这个和三数之和差不多,区别在于多进行一次循环,而且在计算四数的和的时候,要注意转成long类型(不转的话有一组测试用例死活通不过,加起来越界了),而且,在每次循环的时候 ,可以做一些判断来减少循环的次数,比如当前nums[i]如果大于target,退出;当前nums[i]和紧跟着的三个数之和大于target,退出。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int n=nums.length;
List<List<Integer>> res = new ArrayList<>();
int left=0,right=n-1;
for(int i=0;i<n-3;i++){ //保证右侧有3个
if(i>0 && nums[i]==nums[i-1]){
continue;
}
if ((long) nums[i]+nums[i+1]+nums[i + 2]+nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[n-3] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
for(int j=i+1;j<n-2;j++){
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i]+nums[j]+nums[j + 1]+nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
left = j+1;
right = n-1;
while(left<right){
int k=nums[i]+nums[j]+nums[left]+nums[right];
if(k==target){
res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
left++;
while(left<right && nums[left]==nums[left-1]){
left++;
}
right--;
while(left<right && nums[right]==nums[right+1]){
right--;
}
}else if(k<target){
left++;
}else{
right--;
}
}
}
}
return res;
}
}