leetcode题解之两数之和 && 三数之和

﹏ヽ暗。殇╰゛Y 2022-05-15 01:47 171阅读 0赞

1.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的**两个**数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

由于只有一种答案，可以声明一个只有两个元素的数组来储存结果

class Solution {
        public int[] twoSum(int[] nums, int target) {
            //法一：暴力解法
            /*int[] res = new int[2];  //用来储存结果
            for (int i = 0;i < nums.length-1;i++){
                int tmp = target - nums[i];
                for (int j = i+1;j < nums.length;j++){
                    if (nums[j] == tmp){ //判断两数之和是否符合
                        res[0] = i;
                        res[1] = j;
                        break;//答案只有一种，所以可以跳出循环
                    }
                }
            }
            return res;*/
           //法二：Map 键值对应 方便查找下标及其值
         Map<Integer,Integer> map = new HashMap<>();
            int[] res = new int[2];//储存答案
            for (int i = 0;i < nums.length;i++){
                int tmp = target - nums[i];
                if (map.containsKey(tmp)){ //判断map中的Key值是否包含tmp值
                    res[0] = map.get(tmp);
                    res[1] = i;
                    break;
                }
                map.put(nums[i],i);//将数组的值和下标同时推入map中
            }
            return res;
        }
    }

15.三数之和

给定一个包含 *n* 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c = *0 ？找出所有满足条件且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

public List<List<Integer>> threeSum(int[] nums)  {  
            Set<List<Integer>> set = new HashSet<>();//利用set无重复元素,排除重复答案		
             Arrays.sort(nums);//排序
             for(int i = 0;i<nums.length-2;i++){
            	 if(nums[i]>0)break;
            	 if(i > 0 && nums[i-1] == nums[i])continue;//排除第一位的重复项  
            	 int target = -nums[i];
              //转化为两数之和问题，往后遍历，后面两数和需要满足等于target即可
            	 int j = i + 1;//从j往后遍历
            	 int k = nums.length-1;//从k往前遍历
                while(j < k) {
                    int tmp = nums[j]+nums[k];
                	if(tmp == target){
                      List<Integer> list = new ArrayList<Integer>();                 
                      list.add(nums[i]);
                      list.add(nums[j]);
                      list.add(nums[k]);
                      set.add(list);  
                      j++;
                      k--;
                  }
                  if(tmp<target)j++;
                  if(tmp>target)k--;
           }   
             }
             List<List<Integer>> result = new ArrayList<>(set);//将set转换为list
             return result;
             }