TwoSum之Java实现-创新互联

一、题目

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].

成都创新互联基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽，联通大带宽，移动大带宽，多线BGP大带宽租用,是为众多客户提供专业服务器托管报价，主机托管价格性价比高，为金融证券行业成都IDC机房托管，ai人工智能服务器托管提供bgp线路100M独享，G口带宽及机柜租用的专业成都idc公司。

二、题目理解

给定一个整型数组以及一个目标值，求数组中两个相加等于目标值的元素的索引。此题假设给定的数组中一定有两个元素相加等于目标值。

三、实现代码

1、第一种实现方式
使用暴力搜索的方式，用双层for循环遍历数组，拿数组的每一个元素与其他元素相加之后与目标值进行对比，找出符合要求的两个元素。
实现代码如下：

public int[] twoSum01(int[] nums, int target) {
    int[] result = 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) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}

2、第二种实现方式
第一种实现方式在最坏的情况下的时间复杂度为O(n²)，执行时间较长，不是一种比较好的实现方式，下面是第二种实现方法。
定义一个Map，遍历数组，每次都用目标值减去数组当前值得到差值temp，并判断temp是否存在于Map中，如不存在，则将数组当前值和索引存入Map中；如存在，则取出temp对应的索引值。
实现代码如下：

public int[] twoSum02(int[] nums, int target) {
    HashMap<Integer, Integer> tempMap = new HashMap<Integer, Integer>();
    int[] resultArr = new int[2];
    for(int i = 0; i < nums.length; i++) {
        // 用target减去数组当前值
        int temp = target - nums[i];
        // 判断HashMap中是否包含temp
        if(tempMap.get(temp) != null) {
            resultArr[0] = tempMap.get(temp);
            resultArr[1] = i;
            break;
        } else {
            tempMap.put(nums[i], i);        // 如不包含，就将当前值存入Map中
        }
    }
    return resultArr;
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证，机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

当前文章：TwoSum之Java实现-创新互联
文章出自：https://www.cdcxhl.com/article18/dpecdp.html

成都网站建设公司_创新互联，为您提供自适应网站、响应式网站、电子商务、面包屑导航、微信公众号、移动网站建设

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容