欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定一个乱序数组a,找到所有两个和为target的数组下标index1,index2

程序员文章站 2024-03-15 20:21:00
...

给定一个乱序数组a,找到所有两个和为target的数组下标index1,index2

使用hash_map,时间复杂度为o(n),空间复杂度为o(n).

Exp:

a{ 2, 3, 1, 4, 5, 6, 7 },target=6;

输出:0    3

          2    4

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class 乱序数组找下标 {

	public static void main(String[] args) {
		int[] array={ 2, 3, 1, 4, 5, 6, 7 };
		System.out.println(find(array,6));

	}
	public static List<List<Integer>> find(int[] array,int target){
		List<List<Integer>> result=new LinkedList<>();
		if(array==null || array.length<1){
			return result;
		}
		HashMap<Integer,Integer> map=new HashMap<>();
		for(int i=0;i<array.length;i++){
			map.put(array[i], i);
		}
		Arrays.sort(array);
		int start=0;
		int end=array.length-1;
		while(start<end){
			int sum=array[start]+array[end];
			if(sum==target){
				LinkedList<Integer> list=new LinkedList<>();
				list.add(map.get(array[start]));
				list.add(map.get(array[end]));
				result.add(list);
				start++;
				end--;
			}else if(sum<target){
				start++;
			}else{
				end--;
			}
		}
		return result;
	}

}

 

相关标签: 数据结构

推荐阅读