力扣题目-两数字和(三种解法,C++,java,python实现)

简介: 力扣题目-两数字和(三种解法,C++,java,python实现)

题目:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。


示例:


给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]


这里学习的主要是方法,之所以再用python、java实现,是因为我最近在学习这两门语言,希望在此基础是得到巩固。


C++


1.暴力

暴力算法时间复杂度O(n²),空间复杂度O(1)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
              for(int j=i+1;j<nums.size();j++){
                  if(nums[i]+nums[j]==target){
                      ans.push_back(i);
                      ans.push_back(j);
                      return ans;
                  }
              }
        }
        return ans;
    }
};


2.排序+双指针法

这里先将数组排序好O(nlogn),再利用双指针法遍历一遍O(n)得到结果。

为了保存下标信息另开了一个数组

时间复杂度O(nlogn),空间复杂度O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        vector<int> temp;
        temp=nums;
        int n=temp.size();
       sort(temp.begin(),temp.end());
       int i=0,j=n-1;
       while(i<j){  
           if(temp[i]+temp[j]>target)j--;
          else if(temp[i]+temp[j]<target)i++;
          else break; 
       }
       if(i<j){
      for(int k=0;k<n;k++){
          if(i<n&&nums[k]==temp[i]){
              ans.push_back(k);
              i=n;
          }
         else if(j<n&&nums[k]==temp[j]){
              ans.push_back(k);
              j=n;
          }
          if(i==n&&j==n)return ans;
      }
      }
        return ans;
    }
};


3.hash法

利用unordered_map数组构造映射,遍历nums[i]时,看target-nums[i]是否存在hash表中即可

时间复杂度O(n),空间复杂度O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
       unordered_map<int,int>hashmap;
       for(int i=0;i<nums.size();i++){
           if(hashmap[target-nums[i]]
          &&hashmap[target-nums[i]]!=i+1){
          //防止利用同个元素
               ans.push_back(i);
               ans.push_back(hashmap[target-nums[i]]-1);
               return ans;
           }
        hashmap[nums[i]]=i+1;
        //将hash表对应下标+1,防止处理下标为0的情况
       }
       return ans;
    }
};


总结:

实际在提交过程中,方法2,3差距不太,1最慢。


未完待续


Python


暴力

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]
        return []


排序+双指针

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp=nums.copy()
        temp.sort()
        i=0
        j=len(nums)-1
        while i<j:
            if (temp[i]+temp[j])>target:
                j=j-1
            elif (temp[i]+temp[j])<target:
                i=i+1
            else:
                break
        p=nums.index(temp[i])
        nums.pop(p)
        k=nums.index(temp[j])
        if k>=p:
            k=k+1
        return [p,k]


hash

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashset={}
        for i in range(len(nums)):
            if hashset.get(target-nums[i]) is not None :
                return [hashset.get(target-nums[i]),i]
            hashset[nums[i]]=i


java


暴力

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans=new int[2];
        for(int i=0;i<nums.length;i++){
              for(int j=i+1;j<nums.length;j++){
                  if(nums[i]+nums[j]==target){
                      ans[0]=i;
                      ans[1]=j;
                    return ans;
                  }
              }      
    }
    return ans;
    }
}


排序+双指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int m=0,n=0,k,board=0;
        int[] res=new int[2];
        int[] tmp1=new int[nums.length];
        System.arraycopy(nums,0,tmp1,0,nums.length);
        Arrays.sort(nums);
        for(int i=0,j=nums.length-1;i<j;){
            if(nums[i]+nums[j]<target)
                i++;
            else if(nums[i]+nums[j]>target)
                j--;
            else if(nums[i]+nums[j]==target){
                m=i;
                n=j;
                break;
            }
        }
        for(k=0;k<nums.length;k++){
            if(tmp1[k]==nums[m]){
                res[0]=k;
                break;
            }
        }
        for(int i=0;i<nums.length;i++){
            if(tmp1[i]==nums[n]&&i!=k)
                res[1]=i;
        }
        return res;
    }
}


hash

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
       return new int[] {-1,-1};
    }}
目录
打赏
0
0
0
0
1
分享
相关文章
|
18天前
|
Java Redis 面试题集锦 常见高频面试题目及解析
本文总结了Redis在Java中的核心面试题,包括数据类型操作、单线程高性能原理、键过期策略及分布式锁实现等关键内容。通过Jedis代码示例展示了String、List等数据类型的操作方法,讲解了惰性删除和定期删除相结合的过期策略,并提供了Spring Boot配置Redis过期时间的方案。文章还探讨了缓存穿透、雪崩等问题解决方案,以及基于Redis的分布式锁实现,帮助开发者全面掌握Redis在Java应用中的实践要点。
57 6
校招 Java 面试基础题目解析及学习指南含新技术实操要点
本指南聚焦校招Java面试,涵盖Java 8+新特性、多线程与并发、集合与泛型改进及实操项目。内容包括Lambda表达式、Stream API、Optional类、CompletableFuture异步编程、ReentrantLock与Condition、局部变量类型推断(var)、文本块、模块化系统等。通过在线书店系统项目,实践Java核心技术,如书籍管理、用户管理和订单管理,结合Lambda、Stream、CompletableFuture等特性。附带资源链接,助你掌握最新技术,应对面试挑战。
49 2
Java 校招面试题目合集及答案 120 道详解
这份资料汇总了120道Java校招面试题目及其详细答案,涵盖Java基础、JVM原理、多线程、数据类型、方法重载与覆盖等多个核心知识点。通过实例代码解析,帮助求职者深入理解Java编程精髓,为校招面试做好充分准备。无论是初学者还是进阶开发者,都能从中受益,提升技术实力和面试成功率。附带的资源链接提供了更多学习材料,助力高效备考。
64 3
Java 与 C++ 区别深入剖析及应用实例详解
本文深入剖析了Java和C++两种编程语言的区别,从编译与执行机制、面向对象特性、数据类型与变量、内存管理、异常处理等方面进行对比,并结合游戏开发、企业级应用开发、操作系统与嵌入式开发等实际场景分析其特点。Java以跨平台性强、自动内存管理著称,适合企业级应用;C++则因高性能和对硬件的直接访问能力,在游戏引擎和嵌入式系统中占据优势。开发者可根据项目需求选择合适语言,提升开发效率与软件质量。附面试资料链接:[点此获取](https://pan.quark.cn/s/4459235fee85)。
49 0
校招 java 面试基础题目及解析
本文围绕Java校招面试基础题目展开,涵盖平台无关性、面向对象特性(封装、继承、多态)、数据类型、关键字(static、final)、方法相关(重载与覆盖)、流程控制语句、数组与集合、异常处理等核心知识点。通过概念阐述和代码示例,帮助求职者深入理解并掌握Java基础知识,为校招面试做好充分准备。文末还提供了专项练习建议及资源链接,助力提升实战能力。
88 0
|
1月前
|
力扣第一道困难题《3. 无重复字符的最长子串》,c++
首先我们看到这个题是肯定有一种暴力的硬解思路的,那就是将两个vector直接链接起来,然后再排序后,直接返回中间值,这个方法实现起来还是非常容易的,
30 0
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
141 12
|
7月前
|
Java和C++
Java和C++
106 15
|
9月前
|
C++ 程序员的 Java 指南
一个 C++ 程序员自己总结的 Java 学习中应该注意的点。
73 5
WK
|
8月前
|
C++和Java哪个更好用
C++和Java各具优势,选择取决于项目需求、开发者偏好及目标平台特性。C++性能出色,适合游戏、实时系统等;Java平台独立性强,适合跨平台、安全敏感应用。C++提供硬件访问和灵活编程范式,Java有自动内存管理和丰富库支持。两者各有千秋,需根据具体需求选择。
WK
192 1

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等