【LeetCode】Two Sum问题

迈不过友情╰ 2022-05-26 09:48 272阅读 0赞

1.Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路:

数组无序,我们遍历数组时,判断其与target的差值,如果差值在数组中,并且不是自身,那么就是符合条件的,返回两个值的索引位置就可以;我们判断差值是否在数组中,并且如果存在快速定位,通过hashmap实现

  1. class Solution {
  2. public int[] twoSum(int[] nums, int target) {
  3. if(nums == null || nums.length == 0)
  4. return null;
  5. HashMap<Integer,Integer> map = new HashMap<>();
  6. for(int i=0;i<nums.length;i++){
  7. //计算差值
  8. int diff = target-nums[i];
  9. //如果包含,则返回差值的索引位置+当前元素的索引位置
  10. if(map.containsKey(diff)){
  11. return new int[]{map.get(diff),i};
  12. }
  13. //不包含的话,将元素放入map中
  14. map.put(nums[i],i);
  15. }
  16. return null;
  17. }
  18. }

167.Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

思路:

给定有序的数组,找出其中两个元素的和为目标值。
很简单,两个变量,一个指向数组尾部,一个指向数组头部,如果相加为目标值,返回起始+1;如果小于,则将begin后移;如果大于,则将end前移;如果begin

  1. class Solution {
  2. public int[] twoSum(int[] numbers, int target) {
  3. if(numbers == null || numbers.length == 0)
  4. return null;
  5. int begin = 0;
  6. int end = numbers.length-1;
  7. while(begin < end){
  8. if(target == numbers[begin]+numbers[end])
  9. return new int[]{
  10. begin+1,end+1};
  11. else if(target < numbers[begin]+numbers[end])
  12. end--;
  13. else
  14. begin++;
  15. }
  16. return null;
  17. }
  18. }

653.Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 9

Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 28

Output: False

思路:

求得二叉搜索树中两个树节点的值为目标值
对于遍历过的结点,应该保存下来,在hashSet中,以便于在进行深度遍历DFS的时候将目前遍历的结点与目标值的差值是否在hashSet中,如果存在,就返回false,否则将当前结点加入hashSet中,继续递归遍历该结点的左右子树

  1. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
  2. import java.util.*;
  3. class Solution {
  4. Set<Integer> set = new HashSet<>();
  5. public boolean findTarget(TreeNode root, int k) {
  6. if(root == null)
  7. return false;
  8. if(set.contains(k - root.val))
  9. return true;
  10. else
  11. set.add(root.val);
  12. return findTarget(root.left,k)||findTarget(root.right,k);
  13. }
  14. }

发表评论

表情:
评论列表 (有 0 条评论,272人围观)

还没有评论,来说两句吧...

相关阅读

    相关 mysql sum() NULL 问题

    今天在客户反馈线上数据出现了异常,如下图所示,正常值应该是百分百以内的,而且这个数值是随机出现的,刷新几下可能出现一次。 ![watermark_type_ZmFuZ3poZ

    相关 2sum问题和3sum问题

    算法 这个书,190页介绍了 这两个问题 。 2sum的意思是 在一组数中,找到 两个数的和为零。有多少个这样的组合。 3sum是 找 有多少三个数的组合 ,他们的和为零