算法简记- 两数和

1、// . 两数之和

var twoSum = function(nums, target) {
    if (!nums.length) {
        return;
    }
    let hasMap = {};
    let stack = [];
    for (let i = 0, len = nums.length; i < len; i++) {
        let cur = nums[i];
        let tarNum = target - cur;
        if (hasMap[tarNum] !== undefined && i != hasMap[tarNum]) {
            stack.push(hasMap[tarNum], i);
        } else {
            hasMap[cur] = i;
        }
    }
    return stack;
};

2、// 三数和

var threeSum = function(nums) {
    let res = [];
    if (!nums || nums.length < 3) {
        return res;
    }
    let n = nums.length;
    // 排序
    nums.sort((a, b) => a-b);
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) { // 直接结束
            break;
        }
        if (i > 0 && nums[i] === nums[i-1]){
            continue;
        }
        let left = i + 1;
        let right = n - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--; // 减小
            } else if (sum < 0) {
                left++; // 增加
            } else {
                res.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
};



var threeSum = function(nums) {
    // 最左侧值为定值，右侧所有值进行两边推进计算
    let res = [];
    nums.sort((a, b) => a - b);
    let size = nums.length;
    if (nums[0] <= 0 && nums[size - 1] >= 0) {
      // 保证有正数负数
      let i = 0;
      while (i < size - 2) {
        if (nums[i] > 0) break; // 最左侧大于0，无解
        let first = i + 1;
        let last = size - 1;
        while (first < last) {
          if (nums[i] * nums[last] > 0) break; // 三数同符号，无解
          let sum = nums[i] + nums[first] + nums[last];
          if (sum === 0) {
            res.push([nums[i], nums[first], nums[last]]);
          }
          if (sum <= 0) {
            // 负数过小，first右移
            while (nums[first] === nums[++first]) {} // 重复值跳过
          } else {
            while (nums[last] === nums[--last]) {} // 重复值跳过
          }
        }
        while (nums[i] === nums[++i]) {}
      }
    }
  
    return res;
  };

3、// 多数和的模板

var twoSum = function(nums, target) {
    let nums1 = [].concat(nums); // 保留之前顺序，确保拿到正确的索引
    nums.sort((a, b) => a - b);
    let lo = 0, hi = nums.length - 1;
    let result = [];
    while (lo < hi) {
        let left = nums[lo];
        let right = nums[hi];
        let res = nums[lo] + nums[hi];
        if (res < target) {
            while (lo < hi && nums[lo] === left) lo++;
        } else if (res > target) {
            while (lo < hi && nums[hi] === right) hi--;
        } else {
            result.push(nums1.indexOf(nums[lo]));
            result.push(nums1.lastIndexOf(nums[hi])); // 从后取索引，防止拿到相同的索引
            while (lo < hi && nums[lo] === left) lo++;
            while (lo < hi && nums[hi] === right) hi--;
        }
    }
    return result;
};