ksum

就是查找一个列表中是否存在k个值等于某个目标值, 比如leetcode第一题就是一个twoSum的问题

leetcode#1

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

或者借用一个map

var twoSum = function (nums, target) {
  const record = new Map();
  for (let i = 0, len = nums.length; i < len; i++) {
    const num = nums[i];
    if (record.get(target - num) !== undefined) {
      return [record.get(target - num), i];
    } else {
      record.set(num, i);
    }
    // record.set(nums[i], i);
  }
};

leetcode#167

在一个有序列表中查找两个数相加等于某个特定值， 这个就是典型的采用对撞指针来实现的

var twoSum2 = function (numbers: number[], target: number) {
	let i = 0
	let j = numbers.length - 1
	while (i < j) {
		if (numbers[i] + numbers[j] === target) {
			return [i + 1, j + 1]
		} else if (numbers[i] + numbers[j] > target) {
			j--
		} else {
			i++
		}
	}
	throw new Error('the input is has no solution.')
}

找出所有两数和为目标值的组合

function twoSum(arr, target) {
  const sortedArr = arr.sort((a, b) => a - b);
  const ret = [];
  let i = 0,
    j = sortedArr.length - 1;

  while (i < j) {
    const sum = sortedArr[i] + sortedArr[j];
    if (sum === target) {
      ret.push([sortedArr[i], sortedArr[j]]);
      i++;
      j--;
    } else if (sum < target) {
      i++;
    } else if (sum > target) {
      j--;
    }
  }

  return ret;
}

两数相加的变种， 就是数据有重复的时候怎么办

还有一一个办法就是在排序之后去重

function twoSumRepeat(arr, target) {
  const sortedArr = arr.sort((a, b) => a - b);
  console.log(sortedArr);

  const ret = [];
  let i = 0,
    j = sortedArr.length - 1;

  while (i < j) {
    const sum = sortedArr[i] + sortedArr[j];
    if (sum === target) {
      const temp = [sortedArr[i], sortedArr[j]];
      ret.push(temp);
      // 在这里过滤重复的元素
      while (sortedArr[i + 1] === temp[0]) {
        i++;
      }
      while (sortedArr[j - 1] === temp[1]) {
        j--;
      }
      i++;
      j--;
    } else if (sum < target) {
      i++;
    } else if (sum > target) {
      j--;
    }
  }

  return ret;
}
function deleteRepeat(sortArr) {
  if (!sortArr || sortArr.length === 0) {
    return [];
  }
  const result = [];
  result.push(sortArr[0]);
  let pre = sortArr[0];
  let i = 1;
  while (i < sortArr.length) {
    if (pre !== sortArr[i]) {
      result.push(sortArr[i]);
      pre = sortArr[i];
    }
    i++;
  }
  return result;
}

leetcode#15

找出三个不相同序号的数等于某个值

var threeSum = function (nums, target = 0) {
  nums.sort(function (a, b) {
    return a - b;
  });
  console.log(nums);
  const result = [];
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    let left = i + 1;
    let right = len - 1;

    while (left < right && left !== i && right !== i) {
      let threeSum = nums[i] + nums[left] + nums[right];
      if (threeSum === target) {
        const temp = [nums[i], nums[left], nums[right]];

        result.push(temp);
        while (nums[left] === temp[1] && left < right) {
          left++;
        }
        while (nums[right] === temp[2] && left < right) {
          right--;
        }
      }
      if (threeSum < target) {
        left++;
      }
      if (threeSum > target) {
        right--;
      }
    }
    while (i < len - 1 && nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return result;
};