死磕算法系列文章
- 干货 | 手撕十大经典排序算法
- 剑指offer | 认识面试
- 剑指offer | 面试题2：实现Singleton模式
- 剑指offer | 面试题3：二维数组的查找
- 剑指offer | 面试题4：替换空格
- 剑指offer | 面试题5：从尾到头打印链表
- 剑指offer | 面试题6：重建二叉树
- 剑指offer | 面试题7：用两个栈实现队列
- 剑指offer | 面试题8：旋转数组的最小数字
- 剑指offer | 面试题9：斐波那契数列
- 剑指offer | 面试题10：青蛙跳台阶问题
- 剑指offer | 面试题11：矩阵覆盖
- 剑指offer | 面试题12：二进制中1的个数
- 剑指offer | 面试题13：数值的整数次方
- 剑指offer | 面试题14：打印从1到最大的n位数
- 剑指offer | 面试题15：删除链表的节点
- 剑指offer | 面试题16：将数组中的奇数放在偶数前
- 剑指offer | 面试题17：链表中倒数第k个节点
- 剑指offer | 面试题18：反转链表
- 剑指offer | 面试题19：合并两个有序链表
- 剑指offer | 面试题20：判断二叉树A中是否包含子树B
- 剑指offer | 面试题21：二叉树的镜像
- 剑指offer | 面试题22：顺时针打印矩阵
- 剑指offer | 面试题23：包含min函数的栈
- 剑指offer | 面试题24：栈的压入、弹出序列
- 剑指offer | 面试题25：从上到下打印二叉树
- 剑指offer | 面试题26：二叉搜索树的后序遍历序列
- 剑指offer | 面试题27：二叉树中和为某一值的路径
- 剑指offer | 面试题28：复杂链表的复制
- 剑指offer | 面试题29：二叉搜索树转换为双向链表
- 剑指offer | 面试题30：字符串的排列
- 剑指offer | 面试题31：数组中出现次数超过一半的数字
- 剑指offer | 面试题32：最小的k个数
- 剑指offer | 面试题33：连续子数组的最大和
- 剑指offer | 面试题34：1～n 整数中 1 出现的次数
- 剑指offer | 面试题35：把数组排成最小的数
- 剑指offer | 面试题36：丑数
- 剑指offer | 面试题37：第一个只出现一次的字符
- 剑指offer | 面试题38：数组中的逆序对
- 剑指offer | 面试题39：两个链表的第一个公共节点
- 剑指offer | 面试题40：数组中数字出现的次数
- 剑指offer | 面试题41：二叉树的深度
- 剑指offer | 面试题42：平衡二叉树
“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：
代码语言：javascript复制输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
代码语言：javascript复制输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
方法一：双指针
算法流程:
- 初始化：双指针i, j分别指向数组nums的左右两端(俗称对撞双指针) 。
- 循环搜索：当双指针相遇时跳出；
- 计算和s = nums[i] nums[j] ；
- 若s > target，则指针j向左移动，即执行j=j- 1 ;
- 若s < target，则指针i向右移动，即执行i=i 1 ;
- 若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)，
代码语言：javascript复制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-/
