暑假牛客网刷题day1:Java数学之美（一）
【摘要】 在这里我给大家推荐一款不错刷算法学习网站：点击这处链接牛客网；牛客网作为国内内容超级丰富的 IT 题库，各种东西看的我眼花缭乱，题库+面试+学习+求职+讨论+大厂内推等等服务，堪称"互联网求职神器"。它好就好在不只是一个刷题的平台，还是一个交流学习的平台，发个问题贴总有热心的大佬帮助。两数之和描述：两数之和给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起...
在这里我给大家推荐一款不错刷算法学习网站：；牛客网作为国内内容超级丰富的 IT 题库，各种东西看的我眼花缭乱，题库+面试+学习+求职+讨论+大厂内推等等服务，堪称
"互联网求职神器"。它好就好在不只是一个刷题的平台，还是一个交流学习的平台，发个问题贴总有热心的大佬帮助。
两数之和
描述：
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
示例1
输入：[3,2,4],6
返回值：[2,3]
说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2
输入：[20,70,110,150],90
返回值：[1,2]
说明：20+70=90
数组遍历分析：
首先我们能够很自然地想到暴力遍历数组的这样一个方法，两层遍历，第一层确定第一个数，第二层确定第二个数，从而完成题目的要求。
import java.util.*;
public class Solution {
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("No two sum solution");
}
}
hash表分析：
使用Map来降低时间复杂度，遍历数组，如果没有 （target - 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
HashMap<Integer, Integer> map = new HashMap<>();
//遍历数组
for (int i = 0; i < numbers.length; i++) {
//将不包含target - numbers[i]，装入map中，包含的话直接返回下标
if(map.containsKey(target - numbers[i]))
return new int[]{map.get(target - numbers[i])+1, i+1};
else
map.put(numbers[i], i);
}
throw new IllegalArgumentException("No solution");
}
}三数之和
链接通往之处：
思路分析：
这道题要求的不再是返回索引值，因此先排序，然后使用双指针的思路是可行的。具体算法是先对原数组进行一次排序，然后一层循环固定一个元素，循环内部利用双指针找出剩下的两个元素。
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
int n = num.length;
//不够三元组 fast-template
if(n < 3)
return res;
//排序
Arrays.sort(num);
for(int i = 0; i < n - 2; i++){
if(i != 0 && num[i] == num[i - 1])
continue;
//后续的收尾双指针
int left = i + 1;
int right = n - 1;
//设置当前数的负值为目标
int target = -num[i];
while(left < right){
//双指针指向的二值相加为目标，则可以与num[i]组成0
if(num[left] + num[right] == target){
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[left]);
temp.add(num[right]);
res.add(temp);
while(left + 1 < right && num[left] == num[left + 1])
//去重
left++;
while(right - 1 > left && num[right] == num[right - 1])
//去重
right--;
//双指针向中间收缩
left++;
right--;
}
//双指针指向的二值相加大于目标，右指针向左
else if(num[left] + num[right] > target)
right--;
//双指针指向的二值相加小于目标，左指针向右
else left++;
}
}
return res;}
}✨原创不易，还希望各位大佬支持一下
👍点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️评论，你的意见是我进步的财富！
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）