剑指offer | 面试题43：和为s的两个数字

千羽

发布于 2022-02-23 15:39:02

2510

发布于 2022-02-23 15:39:02

死磕算法系列文章

“Leetcode : https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_43_twoSum/Solution.java

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

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

示例 1：

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

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

方法一：双指针

算法流程:

初始化：双指针i, j分别指向数组nums的左右两端(俗称对撞双指针) 。
循环搜索：当双指针相遇时跳出；
1. 计算和s = nums[i] + nums[j] ；
2. 若s > target，则指针j向左移动，即执行j=j- 1 ;
3. 若s < target，则指针i向右移动，即执行i=i+1 ;
4. 若s = target，立即返回数组[nums[i], nums[[j]] ;
返回空数组，代表无和为target的数字组合。

复杂度分析:

时间复杂度O(N) : N为数组nums的长度；双指针共同线性遍历整个数组。
空间复杂度0(1) ：量i, j使用常数大小的额外空间。

package com.nateshao.sword_offer.topic_43_twoSum;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @date Created by 邵桐杰 on 2022/1/25 8:23
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        for (int i : result) {
            System.out.println("i1 = " + i);// i1 = 7   i1 = 2
        }
    }
    /**
     * 双指针 O(1)
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int cur = nums[left] + nums[right];
            if (cur == target) return new int[]{nums[left] , nums[right]};
            else if (cur > target) right--;
            else left++;
        }
        return new int[]{};
    }
}

方法二：HashMap，HashSet

使用hash表一次遍历，时间复杂度O(N)，空间复杂度O(N)，

package com.nateshao.sword_offer.topic_43_twoSum;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @date Created by 邵桐杰 on 2022/1/25 8:23
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        for (int i : result) {
            System.out.println("i1 = " + i);
        }
        int[] twoSum3 = twoSum3(nums, target);
        for (int i : twoSum3) {
            System.out.println("i3 = " + i);
        }

    }

    /**
     * HashSet O(n)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        Set<Object> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(target - num)) {
                set.add(num);
            } else {
                return new int[]{num, target - num};
            }
        }
        return new int[]{};
    }
    /**
     * HashMap
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum3(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],i);
        }

        int[] result = new int[2];
        for (int num : nums) {
            int value =  hashMap.getOrDefault((target-num),-1);
            // System.out.println("key Three 对应的 value: " + value);
            if (value!= -1 && value != hashMap.get(num)) {
                result[0] = num;
                result[1] = target-num;
            }
        }
        return result;
    }
}

参考链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/mian-shi-ti-57-he-wei-s-de-liang-ge-shu-zi-shuang-/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-01-26，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树