求和系列

[TOC]

一、1-两数之和

1.1 题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

1.2 解法

1.2.1 哈希表法

用空间换时间，就是我们可以用哈希表映射的方法，先把数组里所有元素的值作为key，下标作为value存进hashmap里，从hashmap里查找元素的时间复杂度近似常数，即O(1)。

• 思路
  • 先将数组存放在Map(值，索引值)中
  • 然后在Map找是否有这个值
  • 为了避免重复利用同样的元素，要做判断和删除处理。

var twoSum = function (nums, target) {
    let len = nums.length;
    let map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(nums[i], i);
    }
    let arr = [];
    for (let i = 0; i < len; i++) {
        if (map.has(target - nums[i]) && map.get(target - nums[i]) !== i) {
            arr.push(i, map.get(target - nums[i]));
            map.delete(nums[i]);
            map.delete(target - nums[i]);
        }
    }
    return arr;
};

二、2-两数相加

2.1 题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

2.1 解法

/**
         * Definition for singly-linked list.
         * function ListNode(val) {
         *     this.val = val;
         *     this.next = null;
         * }
         */
/**
         * @param {ListNode} l1
         * @param {ListNode} l2
         * @return {ListNode}
         */
var addTwoNumbers = function (l1, l2) {
    let node = new ListNode(0);
    // curr是node的指针
    let curr = node;
    let carry = 0;
    if (!l1) return l2;
    if (!l2) return l1;
    while (l1 || l2) {
        // 避免null没有val属性，也不能为数字0设val属性
        let x = l1 ? l1.val : 0;
        let y = l2 ? l2.val : 0;
        let singleSum = x + y + carry;
        carry = Math.floor(singleSum / 10);
        curr.next = new ListNode(singleSum % 10);
        curr = curr.next;
        l1 = l1 ? l1.next : l1;
        l2 = l2 ? l2.next : l2;
    }
    // 满足9+1=10的情况
    if (carry === 1) {
        curr.next = new ListNode(1);
    }
    return node.next;
};


// 测试用例
function ListNode(val) {
    this.val = val;
    this.next = null;
}

let l1 = new ListNode(2);
let l = l1;
l.next = new ListNode(4);
l = l.next;
l.next = new ListNode(6);
l = l.next;
l.next = null;

let l2 = new ListNode(3);
let s = l2;
s.next = new ListNode(5);
s = s.next;
s.next = new ListNode(7);
s = s.next;
s.next = null;

addTwoNumbers(l1, l2);

三、371-两整数之和

3.1 题目

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:输入: a = 1, b = 2

输出: 3

示例 2:

输入: a = -2, b = 3 输出: 1

3.2 解法

• 思路
  • a^b -> 无进位相加（1001^1011=0010)
  • a&b -> 进位（1001&1011=1001）
  • (a&b)>>1 -> 无相加进位（10010）
  • 不断进行异或，直至进位数都为0

var getSum = function (a, b) {
    let n = a ^ b;
    let m = a & b;
    while (m !== 0) {
        let p = m << 1;
        m = n & p;
        n = n ^ p;
    }
    return n;
};

• 递归写法

var getSum = function (a, b) {
            if (b == 0) return a;
            return getSum(a ^ b, (a & b) << 1);
        }