155 两数之和 II - 输入有序数组(2021.06.07)

167. 两数之和 II - 输入有序数组

链接:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

题目描述见链接内容。

解法1:哈希法

与无序数组的解法相同,声明一个辅助的Map对象,keytarget减去当前遍历的数组的值,valu是当前值的序号

遍历数组的时候判断Map对象中是否存在当前值即可

var twoSum = function(numbers, target) {
    const map = new Map();
    const length = numbers.length;

    for (let i = 0; i < length; i++) {
        const current = numbers[i]
        const index = map.get(current);
        if (index !== undefined) {
            return [index + 1, i + 1]
        } 
        map.set(target - current, i)
    }
};
  • 时间复杂度:${O(N)}$
  • 空间复杂度:${O(N)}$
  • 执行用时:80ms,在所有JavaScript提交中击败了89%的用户,内存消耗:38.3MB,在所有JavaScript提交中击败了46%的用户

解法2:二分法

上一种解法虽然可以解决,但是没有利用『有序上升』数组的特性,提到有序上升的数组,就应该想到利用二分法来解决这个问题

在遍历数组时,对每个成员利用二分法,查找target与其的余数,查找到就返回

最基础的二分查找,不应该不会

var twoSum = function(numbers, target) {
    const length = numbers.length;
    
    for (let i = 0; i < length; i++) {
        const current = numbers[i];
        const index = find(numbers, target - current, i + 1, length - 1);
        if (index > -1) {
            return [i + 1, index + 1]
        }

    }
};

function find(arr, target, start, end) {
  while (start <= end) {
    const mid = ~~((start + end) / 2);
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}
  • 时间复杂度:${O(N Log N)}$,二分查找的时间复杂度是${Log N}$,要对整个数组进行遍历,时间复杂度是${N}$
  • 空间复杂度:${O(1)}$
  • 执行用时:80ms,在所有JavaScript提交中击败了89%的用户,内存消耗:38.3MB,在所有JavaScript提交中击败了46%的用户

解法三:双指针

看了官方题解了解到的解法,很巧妙

声明两个指针,一个在数组的起始位置,另一个在数组的结束位置,求出两个指针的对应的数字之和sum,然后判断sumtarget值的大小,如果sum === target,返回两个指针的序列即可,如果sum < target,那么位于起始位置的指针向前移动一位,相反,如果sum > target,那么位于结束位置的指针向后移动一位

具体的证明可以参考官方题解

var twoSum = function(numbers, target) {
    let start = 0,
        end = numbers.length - 1;
    
    while (start < end) {
        const sum = numbers[start] + numbers[end];
        if (sum === target) {
            return [start + 1, end + 1];
        }
        if (sum > target) {
            end--;
        } else {
            start++;
        }
    }
};
  • 时间复杂度:${O(N)}$
  • 空间复杂度:${O(1)}$
  • 执行用时:80ms,在所有JavaScript提交中击败了89%的用户,内存消耗:38.3MB,在所有JavaScript提交中击败了47%的用户

日记

在题解里写日记,我也是够牛逼的

还是晚上在ICU门口做题,晚上要值班。其实在ICU外值班,并不是很累的,因为基本上一晚上不会有护士来找你,因为一旦护士来找你,说明情况不妙了。只是可能睡得条件太差,灯很亮,地铺很硬,不过我还是挺能兑付的,身体也没什么反应

因为目前看来,不是一个短期能够乐观的过程,时间长了回到北京,能做的事情就很悠闲了,现在能多做一点是一点吧

还是觉得像做梦一样

这几天,ICU门口陪护的家属换了一拨又一拨,有的人不见了,不知道是转危为安、转移到普通病房了,还是发生了谁都不愿意减到的事情

今天新来了一位农村大妈,现在就坐在ICU的门口大声打着电话。她的女儿,因为和家长赌气,觉得家长为了给她的两个哥哥办婚礼,耽误了她的高考,一气之下喝了百草枯。

刷知乎的时候,看到很多关于百草枯的故事,病人来的人是和常人一样,但是实际上没多久就会发生很危险的状况,并且没有办法医治。

现在这个大妈,好像没有太多悲伤、着急的神色,不知道是不想展示给外人,还是不知道百草枯的恐怖。听说这个女孩要转院到郑州了,祝她好运。

上一篇:【Leetcode】155: 最小栈(Python)


下一篇:Qt开发经验小技巧151-155