题意
给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数组中的下标（索引）不同。
示例
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
难度
简单
分析
我相信，大部分球友都能想到暴力破解，即便你是算法小白，以前从来没有刷过 LeetCode。
当然了，没有一点 Java 基础肯定是不行的，所以推荐你先去看看二哥的 Java 进阶之路，最起码刷一个星期把语法先掌握了。
好，所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词（Brute-Force，暴力攻击）。
两层遍历，第一层确定第一个数，第二层确定第二个数，用一个加法运算就可以完成题目的要求。
class Solution {
// 定义一个方法 twoSum，接收一个整数数组 nums 和一个目标值 target
public int[] twoSum(int[] nums, int target) {
// 外层循环遍历数组中的每个元素
for(int i = 0; i < nums.length; i++) {
// 内层循环从当前元素的下一个开始遍历
for(int j = i + 1; j < nums.length; j++) {
// 检查当前选中的两个数之和是否等于目标值
if(nums[i] + nums[j] == target)
// 如果等于目标值，返回这两个数的索引
return new int[]{i, j};
}
}
// 如果遍历完数组都没有找到符合条件的两个数，则抛出异常
throw new IllegalArgumentException("没有找到");
}
}
笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是 $O(n^2)$。
时间复杂度，在算法领域是一个非常重要的概念，一个衡量算法执行时间随输入数据规模增长而增长的度量。在这个特定的 “两数之和” 问题的解法中，时间复杂度是由两层嵌套循环决定。
我在二哥的 Java 进阶之路里有详细地解释过，戳链接了解。
$O(n^2)$ 的时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到 28% 的用户。
能不能优化一下呢？
观察第二个循环，我们是从每个 5人已点赞
5 条评论
回复