给一个有序数组,找出其中和为 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
时间复杂度达到 , 是不可用的算法,凡有序必二分,优化嵌套循环,可以考虑“双指针”。
网友评论