力扣题目-两数字和(三种解法,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};
    }}
相关文章
|
14天前
|
jenkins Shell 测试技术
|
14天前
|
机器学习/深度学习 JSON Java
Java调用Python的5种实用方案:从简单到进阶的全场景解析
在机器学习与大数据融合背景下,Java与Python协同开发成为企业常见需求。本文通过真实案例解析5种主流调用方案,涵盖脚本调用到微服务架构,助力开发者根据业务场景选择最优方案,提升开发效率与系统性能。
151 0
|
14天前
|
安全 jenkins Java
Java、Python、C++支持jenkins和SonarQube(一)
Jenkins 是一个开源的 持续集成(CI)和持续交付(CD) 工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
72 5
|
14天前
|
jenkins Java Shell
Java、Python、C++支持jenkins和SonarQube(全集)
Jenkins 是一个开源的持续集成(CI)和持续交付(CD)工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
111 1
|
14天前
|
jenkins Java 持续交付
|
14天前
|
jenkins Java 测试技术
|
3月前
|
人工智能 Java 测试技术
Java or Python?测试开发工程师如何选择合适的编程语言?
测试工程师如何选择编程语言?Java 还是 Python?多位资深专家分享建议:Python 入门简单、开发效率高,适合新手及自动化测试;Java 生态成熟,适合大型项目和平台开发。建议结合公司技术栈、个人基础及发展方向选择。长远来看,两者兼通更佳,同时关注 Go 等新兴语言。快速学习与实践才是关键。
|
4月前
|
缓存 NoSQL Java
Java Redis 面试题集锦 常见高频面试题目及解析
本文总结了Redis在Java中的核心面试题,包括数据类型操作、单线程高性能原理、键过期策略及分布式锁实现等关键内容。通过Jedis代码示例展示了String、List等数据类型的操作方法,讲解了惰性删除和定期删除相结合的过期策略,并提供了Spring Boot配置Redis过期时间的方案。文章还探讨了缓存穿透、雪崩等问题解决方案,以及基于Redis的分布式锁实现,帮助开发者全面掌握Redis在Java应用中的实践要点。
195 6
|
3月前
|
JSON JavaScript 前端开发
Python+JAVA+PHP语言,苏宁商品详情API
调用苏宁商品详情API,可通过HTTP/HTTPS发送请求并解析响应数据,支持多种编程语言,如JavaScript、Java、PHP、C#、Ruby等。核心步骤包括构造请求URL、发送GET/POST请求及解析JSON/XML响应。不同语言示例展示了如何获取商品名称与价格等信息,实际使用时请参考苏宁开放平台最新文档以确保兼容性。
|
4月前
|
算法 Java 关系型数据库
校招 Java 面试基础题目解析及学习指南含新技术实操要点
本指南聚焦校招Java面试,涵盖Java 8+新特性、多线程与并发、集合与泛型改进及实操项目。内容包括Lambda表达式、Stream API、Optional类、CompletableFuture异步编程、ReentrantLock与Condition、局部变量类型推断(var)、文本块、模块化系统等。通过在线书店系统项目,实践Java核心技术,如书籍管理、用户管理和订单管理,结合Lambda、Stream、CompletableFuture等特性。附带资源链接,助你掌握最新技术,应对面试挑战。
87 2

热门文章

最新文章

推荐镜像

更多