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

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

作者: 子十一刻 | 来源:发表于2022-03-03 10:05 被阅读0次

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

    需求

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

    常规思路

    • 嵌套循环,找到一个数然后遍历下一个数,求和,判断
    • 时间复杂度是 O(n^2),不可用

    功能实现

    /**
     * 常规思路 使用双层循环实现
     * @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

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

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/ocmyrrtx.html