剑指 Offer 57. 和为s的两个数字

作者:神秘网友 发布时间:2021-02-11 18:50:09

剑指 Offer 57. 和为s的两个数字

题意

在一个有序数组里找两个和为s的数字

思路

  • 1??有序,立刻联想到二分查找,我们可以依次遍历数组中的每个数字,然后二分查找另一个数字使得和可以为s。
  • 2??双指针的写法
    • 一开始分别放在最左和最右,对应为最小和最大的数字,记两个指针指向的元素的和为sum
    • 如果sum target,说明太大,则右边的指针应该往左走
    • 如果sum target,说明太小,则左边的指针应该往右走

代码(二分查找)

class Solution {
public:
    int find_pair(vectorint nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left = right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }else if(nums[mid]  target) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
    vectorint twoSum(vectorint nums, int target) {
        for(auto n: nums) {
            int p = find_pair(nums, target - n);
            if(p != -1) {
                return {n, nums[p]};
            }
        }
        return {};
    }
};

代码(双指针法)

class Solution {
public:
    vectorint twoSum(vectorint nums, int target) {
        int cur1 = 0, cur2 = nums.size() - 1;
        while(cur1 != cur2) {
            int sum = nums[cur1] + nums[cur2];
            if(sum == target) {
                return {nums[cur1], nums[cur2]};
            }else if(sum  target) {
                cur2--;
            }else {
                cur1++;
            }
        }
        return {};
    }
};

剑指 Offer 57. 和为s的两个数字 相关文章

  1. 剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算

    剑指 Offer 56 - II. 数组中数字出现的次数 II Offer_56_2 题目详情 解题思路 java代码 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/10 13:43 *//** * 题目描述:在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现

  2. 剑指 Offer 55 - II. 平衡二叉树 + 平衡二叉树(AVL)的判断

    剑指 Offer 55 - II. 平衡二叉树 Offer_55_2 题目描述 方法一:使用后序遍历+边遍历边判断 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/9 20:58 *//** * 题目描述:输入一棵二叉树的根节点,判断该树是不是平衡二叉树。 * 如果

  3. [剑指offer] 重建二叉树

    题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 示例1 输入 [1,2,3,4,5,6,7],

  4. 剑指 Offer 36. 二叉搜索树与双向链表

    = 将一棵BST转化为一个排序的双向循环链表,返回头结点,“head” 表示指向链表中有最小元素的节点。 由于是二叉搜索树,所以最左结点是最小元素的结点。 要有序,所以选择中序遍历。 /*// Definition for a Node.class Node {public: int val; Node* left;

  5. leetcode-剑指19-OK

    // language C with STL(C++)// 剑指19// https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/// 偷师题解class Solution {public:int getnum(string what, char a){int num = 0;int len = what.length();for(int i =0; ilen; i++){if(what

  6. 剑指 Offer 52. 两个链表的第一个公共节点 + 链表 + 第一个公共结点 + 双指针

    剑指 Offer 52. 两个链表的第一个公共节点 Offer_52 题目详情 题解分析 可以使用两个指针 node1,node2 分别指向两个链表 headA,headB 的头结点,然后同时分别逐结点遍历。 当 node1 到达链表 headA 的末尾时,重新定位到链表 headB 的头结点;当 node2 到

  7. 剑指 Offer 53 - I. 在排序数组中查找数字 I + 二分法

    剑指 Offer 53 - I. 在排序数组中查找数字 I Offer_53_1 题目描述 方法一:使用HashMap package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/9 20:10 */import java.util.HashMap;import java.util.Map;/** * 题目描述:统计一个数字在

  8. 剑指 Offer 51. 数组中的逆序对 + 归并排序 + 树状数组

    剑指 Offer 51. 数组中的逆序对 Offer_51 题目描述 方法一:暴力法(双层循环,超时) package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/9 9:12 *//** * 题目详情:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数

  9. 力扣刷题记录(2021.2.9) 剑指 Offer 53 - II. 0~n-1中缺失的数字

    题目描述 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。 示例1 输入: [0,1,3]输出: 2 示例2 输入: [0,1,2,3,4,5,6,7,9]输出: 8 思路:使

  10. 剑指 Offer 50. 第一个只出现一次的字符 + 哈希表 + 有序哈希表

    剑指 Offer 50. 第一个只出现一次的字符 Offer_50 题目详情 方法一:使用无序哈希表 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/8 22:13 */import java.util.HashMap;import java.util.LinkedHashMap;import java.util.Map;/*

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词