剑指offer-和为s的两个数字

和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

思路

利用双指针，左边的指针从数组头部开始，右边的指针从数组的尾部开始，不断缩小查找范围，找到则输出，没有的话，返回[]

代码

function twoSum(arr, target) {
    if (arr.length === 0) {
        return [];
    }

    let left = 0, right = arr.length - 1;

    while (left < right) {
        const leftVal = arr[left];
        const rightVal = arr[right];
        const sum = leftVal + rightVal;
        if (sum < target) {
            left++;
        } else if (sum > target) {
            right--;
        } else {
            return [leftVal, rightVal];
        }
    }

    return [];
}

复杂度分析:

时间复杂度: O(1)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

和为s的两个数字

思路

代码

CATALOG

FEATURED TAGS

FRIENDS