TS数据结构与算法之查找数组中和为目标值的两个元素

给一个有序数组，找出其中和为 n 的两个元素

需求

• 有一个递增的数组[1，2，4，7，11，15]和一个 n = 15
• 数组中有两个数，和是 n，即 4 + 11 = 15
• 写一个函数找出这两个数

常规思路

• 嵌套循环，找到一个数然后遍历下一个数，求和，判断
• 时间复杂度是 ，不可用

功能实现

/**
 * 常规思路 使用双层循环实现
 * @param arr 
 * @param sum 
 */
export const findTwoNumbersByLoop = (
  arr: number[],
  sum: number
): number[] | undefined => {
  const len = arr.length;

  if (!len) return undefined;

  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      const target = arr[i] + arr[j];

      if (target === sum) {
        return [arr[i], arr[j]];
      }
    }
  }

  return undefined;
}

优化算法 - 双指针思路

• 利用递增有序的特性
• 随便找两个数
• 如果和大于n则向前查找
• 如果和小于n则向后查找
• 类似二分法
• 时间复杂度可以降到 O(n)

功能实现

• 定义 start 指向头 end 指向尾，求 arr[start] + arr[end]
• 如果大于n，则 end向前移动
• 如果小于n，则 start 向后移动

/**
 * 优化算法 双指针方式 使用类似二分法
 * O(n)
 */
export const findTwoNumbersByBinary = (
  arr: number[],
  sum: number
): number[] | undefined => {
  const len = arr.length;

  if (!len) return undefined;
  // 初始化索引位置
  let start = 0;
  let end = len - 1;

  while (start < end) {
    const target = arr[start] + arr[end];

    if (target < sum) {
      // 小于目标 start 右移
      start += 1;
    } else if (target > sum) {
      // 大于目标 end 左移
      end -= 1;
    } else {
      // 相等 找到目标
      return [arr[start], arr[end]];
    }
  }

  return undefined;
}

功能测试

export const twoNumbersFunctionalTest = () => {
  const arr = [1, 3, 5, 10, 30, 40, 50];
  // console.log(findTwoNumbersByLoop(arr, 51)); // [1, 50]
  // console.log(findTwoNumbersByLoop(arr, 40)); // [10, 30]
  // console.log(findTwoNumbersByLoop(arr, 43)); // [3, 40]
  // console.log(findTwoNumbersByLoop(arr, 20)); // undefined

  console.log(findTwoNumbersByBinary(arr, 51)); // [1, 50]
  console.log(findTwoNumbersByBinary(arr, 40)); // [10, 30]
  console.log(findTwoNumbersByBinary(arr, 43)); // [3, 40]
  console.log(findTwoNumbersByBinary(arr, 20)); // undefined
};

单元测试

import { findTwoNumbersByBinary, findTwoNumbersByLoop} from '../src/utils';

/**
 * 查找数组中和为目标值的两个项单元测试
 */
describe('查找数组中和为目标值的两个项', () => {
  test('循环方式常规测试', () => {
    const arr = [1, 3, 5, 10, 30, 40, 50];
    expect(findTwoNumbersByLoop(arr, 51)).toEqual([1, 50]);
    expect(findTwoNumbersByLoop(arr, 40)).toEqual([10, 30]);
    expect(findTwoNumbersByLoop(arr, 43)).toEqual([3, 40]);
    expect(findTwoNumbersByLoop(arr, 20)).toBeUndefined();
  })

  test('循环方式空数组测试', () => {
    expect(findTwoNumbersByLoop([], 51)).toBeUndefined();
  });

  test('二分方式常规测试', () => {
    const arr = [1, 3, 5, 10, 30, 40, 50];
    expect(findTwoNumbersByBinary(arr, 51)).toEqual([1, 50]);
    expect(findTwoNumbersByBinary(arr, 40)).toEqual([10, 30]);
    expect(findTwoNumbersByBinary(arr, 43)).toEqual([3, 40]);
    expect(findTwoNumbersByBinary(arr, 20)).toBeUndefined();
  })

  test('二分方式空数组测试', () => {
    expect(findTwoNumbersByBinary([], 51)).toBeUndefined();
  })
});

执行结果：

 PASS  tests/find-two-numbers.test.ts
  查找数组中和为目标值的两个项
    ✓ 循环方式常规测试 (2 ms)
    ✓ 循环方式空数组测试
    ✓ 二分方式常规测试 (1 ms)
    ✓ 二分方式空数组测试 (1 ms)

性能测试

export const twoNumbersPerformanceTest = () => {
  const arr = [1, 3, 5, 10, 11, 12, 13, 14, 18, 20, 22, 25, 27, 29, 30, 31, 33, 36, 38, 40, 50, 90, 100];
  console.time('findTwoNumbersByLoop');
  for (let i = 0; i < 100 * 10000; i++) {
    findTwoNumbersByLoop(arr, 51);
  }
  console.timeEnd('findTwoNumbersByLoop');

  console.time('findTwoNumbersByBinary');
  for (let i = 0; i < 100 * 10000; i++) {
    findTwoNumbersByBinary(arr, 51);
  }
  console.timeEnd('findTwoNumbersByBinary');
};

• findTwoNumbersByLoop: 37.976806640625 ms
• findTwoNumbersByBinary: 16.615234375 ms

时间复杂度达到 , 是不可用的算法，凡有序必二分，优化嵌套循环，可以考虑“双指针”。