前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【每天一道编程系列-2018.2.12】(Ans)

【每天一道编程系列-2018.2.12】(Ans)

作者头像
yesr
发布2019-03-14 12:53:55
3050
发布2019-03-14 12:53:55
举报
文章被收录于专栏:leetcode_solutions

【题目描述】

  Given an array of integers, 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. Please note that your returned answers (both index1 and index2) are not zero-based.    You may assume that each input would have exactly one solution.    Input: numbers={2, 7, 11, 15}, target=9    Output: index1=1, index2=2 

【题目翻译】

  给定一个整数数组,找出其中两个数满足相加等于你指定的目标数字。    要求:这个函数twoSum必须要返回能够相加等于目标数字的两个数的索引,且index1必须要小于index2。请注意一点,你返回的结果(包括index1和index2)都不是基于0开始的。你可以假设每一个输入肯定只有一个结果。

【解题思路】

  创建一个辅助类数组,对辅助类进行排序,使用两个指针,开始时分别指向数组的两端,看这两个下标对应的值是否等于目标值,如果等于就从辅助类中找出记录的下标,构造好返回结果,返回。如果大于就让右边的下标向左移,进入下一次匹配,如果小于就让左边的下标向右移动,进入下一次匹配,直到所有的数据都处理完 

【本题答案】

代码语言:javascript
复制
import java.util.Arrays;

/**
 * @author yesr
 * @create 2018-02-12 下午10:18
 * @desc
 **/
public class Test0212 {
    /**
     * 辅助类
     */
    private static class Node implements Comparable<Node> {
        int val; // 值
        int idx; // 值对应的数组下标

        public Node() {
        }

        public Node(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }

        // 比较方法
        @Override
        public int compareTo(Node o) {
            if (o == null) {
                return -1;
            }
            return this.val - o.val;
        }
    }


    public int[] twoSum(int[] nums, int target) {
// 用于保存返回结果
        int[] result = {0, 0};

// 创建辅助数组
        Node[] tmp = new Node[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tmp[i] = new Node(nums[i], i);
        }

// 对辅助数组进行排序
        Arrays.sort(tmp);

// 记录辅助数组中左边一个值的下标
        int lo = 0;
// 记录辅助数组中右边一个值的下标
        int hi = nums.length - 1;

// 从两边向中间靠陇进行求解
        while (lo < hi) {
// 如果找到结果就设置返回结果,并且退出循环
            if (tmp[lo].val + tmp[hi].val == target) {

                if (tmp[lo].idx > tmp[hi].idx) {
                    result[0] = tmp[hi].idx + 1;
                    result[1] = tmp[lo].idx + 1;
                } else {
                    result[0] = tmp[lo].idx + 1;
                    result[1] = tmp[hi].idx + 1;
                }
                break;
            }
// 如果大于目标值,右边的下标向左移动
            else if (tmp[lo].val + tmp[hi].val > target) {
                hi--;
            }
// 如果小于目标值,左边的下标向右移动
            else {
                lo++;
            }
        }
        return result;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年02月12日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档