两数之和

两数之和:力扣1

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

思路一

最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时,需要注意到每一个位于 x 之前的元素都已经和 x 匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在 x 后面的元素中寻找 target - x。

function twoSum(nums,target){
    for(var i = 0;i < nums.length; i++){
        for(var j = i + 1;j < nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i,j];
            }
        }
    }
    return [];
}

思路二

使用对象(哈希表),可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)

function twoSum(nums,target){
    var obj = {};// 用于记录访问过元素信息 属性名:数组元素 ,属性值:数组元素对应的索引
    for(var i = 0;i < nums.length;i++){
        var x = nums[i];
        if(obj[target-x]>=0){
            // 查找target-x
            return [obj[target-x],i];
        }
        obj[x] = i;
    }
    return [];
}

数组双指针

利用双指针提高数组的遍历效率。

示例:

// 翻转数组 nums
var left = 0;
var right = nums.length-1;
while(left < right){
    //交换位置
    var temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    left++;
    right--;
}

示例:

二分搜索:力扣704

给定有 n 个元素的升序整型数组 nums 和⼀个⽬标值 target,写⼀个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

输⼊:nums = [-1,0,3,5,9,12], target = 9
输出:4
解释:9 出现在 nums 中并且下标为 4
function search(nums,target){
    var left = 0;
    var right = nums.length-1;
    while(left <= right){
        // var mid = left + Math.floor((right - left)/2);
        var mid = Math.floor((left + right)/2);
        if(nums[mid] == target){
            return mid
        }else if(nums[mid] > target){
            right= mid - 1;
        }else if(nums[mid]<target){
            left = mid + 1;
        }
    }
    return -1;
}

示例:

快慢指针:删除有序数组中的重复项:力扣26

给你⼀个有序数组 nums,请你原地删除重复出现的元素,使每个元素只出现⼀次,返回删除后数组的新⻓
度。
不要使⽤额外的数组空间,你必须在原地修改输⼊数组并在使⽤ O(1) 额外空间的条件下完成。

function removeDuplicates(nums){
    var n = nums.length;
    if (n === 0) {
        return 0;
    }
    var fast = 1, slow = 1;
    while (fast < n) {
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}
// 对照官方题解的动态图,更容易看明白
文档更新时间: 2022-04-27 17:40   作者:张老师