“This is the 11th day of my participation in the August Gwen Challenge.

LeetCode number one. Sum of two numbers

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Train of thought

  1. Violence traversal

  2. Hash tables, hash maps to solve this problem

Time complexity, ORDER n.

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
	let map = new Map(a);for (let i = 0; i < nums.length; i++) {
    let cur = nums[i];
    let another = target - cur;
    if (map.has(another)) {
        return [map.get(another), i];
    }
    map.set(cur, i);
  }
  throw new Error('Not found');
};
Copy the code

The sum of three number

LeetCode link

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Note: Repeated triples cannot be included in the answer.

example

Enter nums = [-1.0.1.2, -1, -4] Output: [[-1, -1.2], [...1.0.1]]
Copy the code

Train of thought

  1. So the first step is sort
  2. After you finish shooting from small to large, start traversing the current item
  3. Define two Pointers, I +1 and length-1 respectively
  4. Go to the right and go to the left

Answer key

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var threeSum = function(nums) {
	let len = nums.length;
  let result = [];
  if (len < 3| |! nums)return result;
  / / sorting
  nums.sort((a,b) = > a - b);
  for (let i = 0; i < len; i++) {
    // If the current number is greater than 0, the sum of the following numbers must be greater than 0, so break
    if (nums[i] > 0) break;
    // Unweight, this is very clever, if it is equal to the previous item, then unweight,
    If the first -1 is found, if the second -1 is found, it will repeat the first one
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    let left = i + 1;
    let right = len - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum == 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // The following two lines of code remove the possibility of duplicate arrays
        while (left < right && nums[left] == nums[left + 1]) left++;
        while (left < right && nums[right] == nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) left++;
      else if (sum > 0) right--; }}return result;
};
Copy the code

912. Sort arrays

Leetcode link

describe

Given an integer array nums, please sort the array in ascending order.

demo

Enter: nums = [5.2.3.1] output: [1.2.3.5]
Copy the code

parsing

Use quicksort to solve this problem

/ * * *@param {number[]} nums
 * @return {number[]}* /
var swap = function (arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
var partition = function (arr, left, right) {
    let pivot = Math.floor(Math.random(right - left + 1) + left);
    let current = arr[pivot];
		// There must be an equal sign
    while(left <= right) {
        while(arr[left] < current) {
            left++;
        }
        while(arr[right] > current) {
            right--
        }
        if(left <= right) { swap(arr, left, right); left++; right--; }}}var quickSort = function (arr, left, right) {
    if (left < right) {
        let index = partition(arr, left, right);

        if (left < index - 1) {
            quickSort(arr, left, index - 1);
        }
        if(right > index) { quickSort(arr, index, right); }}};var sortArray = function(nums) {
  if (nums.length <= 1) return nums;
    const len = nums.length;
    return quickSort(nums, 0, len - 1);
};
Copy the code