Java实现LeetCode（两数之和）

2024-04-16 11:42:05

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回[0, 1]

思路一：最直接的思维，两次遍历查询，时间复杂度O(N*N)。

代码：

public static int[] twoSum1(int[] nums, int target) {
		int[] label = new int[2];
		for(int i=0;i<nums.length-1;i++) {
			int tmp = target - nums[i];
			for(int j=i+1;j<nums.length;j++) {
				if(tmp == nums[j]) {
					label[0] = i;
					label[1] = j;
				}
			}
		}
		return label;
	}

思路二：先排序，然后两个指针i,j，i从前开始，j从后开始查找，当nums[i]+nums[j]>target时，j--；当nums[i]+nums[j]<target时，i++；注意排序后，之前的下标数字已经变化了。时间复杂度O(N*Log2N)

代码：

public static int[] twoSum2(int[] nums, int target) {
		int[] label = new int[2];
		int[] tmpArr = new int[nums.length];
		for(int i=0;i<nums.length;i++) {
			tmpArr[i]=nums[i];
		}
		Arrays.sort(nums);
		int i=0;
		int j=nums.length-1;
		while (i<j) {
			if(nums[i]+nums[j]==target) {
				label[0] = nums[i];
				label[1] = nums[j];
				break;
			}else if(nums[i]+nums[j]>target){
				j--;
			}else {
				i++;
			}
		}
		for(int k=0;k<tmpArr.length;k++) {
			if(tmpArr[k]==label[0]) {
				label[0]=k;
			}
			if(tmpArr[k]==label[1]) {
				label[1]=k;
			}
		}
		return label;
	}

思路三：利用空间换时间方式，用hashmap存储数组结构，key为值，value为下标。时间复杂度O(N)。

代码：

public static int[] twoSum3(int[] nums, int target) {
		int[] label = new int[2];
		HashMap<Integer, Integer> hashMap = new HashMap<>();
		for(int i=0;i<nums.length;i++) {
			hashMap.put(nums[i], i);
		}
		for(int i=0;i<nums.length;i++) {
			if(hashMap.containsKey(target-nums[i])&&hashMap.get(target-nums[i])!=i) {
				label[0] = i;
				label[1] = hashMap.get(target-nums[i]);
				break;
			}
		}
		return label;
	}

github地址：https://github.com/xckNull/Algorithms-introduction

到此这篇关于Java实现LeetCode（两数之和）的文章就介绍到这了,更多相关Java实现两数之和内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

vscode刷acm、leetcode的题目

目录简介编译器 Windows 使用 Code Runner 插件运行代码使用 C/C++ 插件编译并调试安装插件配置编译配置 GDB/LLDB 调试器开始调试代码简介 Visual Studio Code(以下简称 VS Code) 是一个由微软开发,同时支持 Windows.Linux 和 macOS 等操作系统且开放源代码的代码编辑器.它是用 TypeScript 编写的,并且采用 Electron 架构.它带有对 JavaScript.TypeScript 和 Node.
Java实现LeetCode（组合总和）

leetcode题目组合总和 -- leetcode 39 题目描述给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合. 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3
Java实现LeetCode（报数）

题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =
Java实现LeetCode（螺旋矩阵）

LeetCode54. 螺旋矩阵 java实现题目难度中给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8
如何用C++制作LeetCode刷题小技巧-错题记录本

一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用
Java实现LeetCode（两数之和）

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =
C++实现LeetCode(170.两数之和之三 - 数据结构设计)

[LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai
C++实现LeetCode(167.两数之和之二 - 输入数组有序)

[LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t
JS求解两数之和算法详解

本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num
使用python实现两数之和的画解算法

题目描述给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],
c语言如何实现两数之和

目录 c语言实现两数之和 c语言中比较两数大小题目要求分析一下 c语言实现两数之和 int *twoSum(int *nums , int numsSize , int target , int *returnSize) { int i = 0 , j = 0; *returnSize = 2; int *a = (int *)malloc(sizeof(int) * 2); for(i = 0;i<numsSize;i++) { for(j=i+1;j<numsSize;j++) { i
C++求两数之和并返回下标详解

目录给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标. ACM模式核心代码模式方法一: 创建vector 添加元素删除元素其他方法二: auto的使用 unordered_map 查找元素是否存在若有unordered_map <int, int> mp;查找x是否在map中类总结: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 tar
C#算法之两数之和

题目给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标. 你可以假设每种输入只会对应一个答案.但是,你不能重复利用这个数组中同样的元素. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] 提示:不能自身相加. 测试用例 [2,7,11,15] 9 预期结果 [0,1] 格式模板 public class S
C++实现LeetCode（三数之和）

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut
关于PHP求解三数之和问题详析

三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 解题思路

Java实现LeetCode（两数之和）

相关推荐

随机推荐