刷题（数组相关leetcode）

77 阅读 0 评论 51 点赞

我是靠谱客的博主超级御姐，最近开发中收集的这篇文章主要介绍刷题（数组相关leetcode），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

16.最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
在这里插入图片描述
思路：遍历计算数组中每一个值与数组中其他两个值的结果，将最接近target的值赋值给结果值

var threeSumClosest = function(nums, target) {
	//对数组进行从下到大的排序
    var nums=nums.sort((a,b)=>a-b);
    var result=nums[0]+nums[1]+nums[2];
    //遍历数组中的每一个数与数组中其他两个数的和
    for(var i=0;i<nums.length-2;i++){
        var l=i+1,r=nums.length-1;
        while(l<r){
            var threeSum=nums[i]+nums[l]+nums[r];
            //最接近target的值赋值给输出结果
            if(Math.abs(threeSum-target)<Math.abs(result-target)){
                result=threeSum;   
            }
            if(threeSum>target){
                r--;
            }else if(threeSum<target){
                l++;
            }else{
                return target;
            }
        }
    }
    return result;
};

26.删除数组中重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

在这里插入图片描述
思路·：遍历数组中每一个值与它的下一个值是否相等，如果不相等，数组下标加1，移到下一个元素，如果相等则删除当前值，数组下标不移动

var removeDuplicates = function(nums) {
	//遍历数组中的元素
    for(var i=0;i<nums.length-1;){
    	//比较当前值与数组值是否相同，如果相同就删除当前值，数组下表不移动
        if(nums[i]==nums[i+1]){
            nums.splice(i,1);
        }else{
            i++;
        }
    }
    return nums.length
};

27.移除元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
在这里插入图片描述
思路：与上题方法一样，遍历数组中的每一个数，与val相同就删除，然后数组下标不动，如果不相同数组加标加1，移到下一个数

var removeElement = function(nums, val) {
    for(var i=0;i<nums.length;){
        if(nums[i]==val){
            nums.splice(i,1);
        }else{
            i++
        }
    }
    return nums.length;
};

41.缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
在这里插入图片描述
思路·：判断1-数组长度的正数是否在数组中出现过，没出现的第一个就是最小的，如果都出现过，那个数组长度加1的数是最小的

var firstMissingPositive = function(nums) {
    for(var i=1;i<=nums.length;i++){
        if(nums.indexOf(i)==-1){
            return i;
        }
    }
    return nums.length+1;
    
};

一个无序，不相等数组中，选取N个数，使其和为sum实现算法
思路：递归数组中每一个数与其他数组成的结果

function arrSum(arr,sum){
	var newArr=[];
	for(var i=0;i<arr.length;i++){
		if(arr[i]==sum){
			//一个数的情况
			newArr.push([arr[i]]);
		}else{
			function dfs(subArr,arr,sum){
				for(var j=0;j<arr.length;j++){
					if(arr[j]==sum){
						//两个数的情况
						newArr.push(subArr.concat(arr[j]))
					}else{
						//多个数的情况
						dfs(subArr.concat(arr[j]),arr.slice(j+1),sum-arr[j]);
					}
				}
			}
			dfs([arr[i]],arr.slice(i+1),sum-arr[i]);
		}
	}
	return newArr;
}

var arr=[-1,-2,0,2,3,1],sum=0;
console.log(arrSum(arr,sum));