算法-求和问题

2019 精帖
算法基础 数据结构
0 11198

问题描述

        给定一个int类型一维数组 a[],和一个int类型的数值 b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表(return new int[]={1,2}),如果没有返回-1(return new int[]={-1,-1})。


算法:用查找表解决问题

实现:

package club.test;

import java.util.HashMap;
import java.util.Map;
/**
 * @author jiajia
 */
public class TestMain3 {
	public static void main(String[] args) {
		int[] a=new int[]{1,2,3,9};
		int step=11;
		int[] res=index(a,step);
		System.out.println(res[0]+" & "+res[1]);
	}
	public static int[] index(int[] a,int step) {
		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(int i=0;i<a.length;i++) {
			if(map.containsKey(step-a[i]))
				return new int[] {map.get(step-a[i]),i};
			else
				map.put(a[i],i);
		}
		return new int[] {-1,-1};
	}
}


留言(0)
猜你喜欢
  • blog 选择排序 - 数据结构

    思想: 对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 用变量i遍历整个数组,用变量j遍历i后面的数组,每次遍历i初始k=i,每次发现a[k]比a[
  • blog 广度优先搜索(bfs、广搜)java实现-数据结构

    广度优先搜索(dfs、深搜)java实现-数据结构 用邻接矩阵表示图的定点之间的关系 如下图的数据结构: 则用邻接矩阵表示为: private static int map[][]={ {0 ,3 ,6
  • blog 迷宫-寻找最短路径

    迷宫-寻找最短路径:广度优先搜索数据结构:队列,链表代码实现:<!DOCTYPE html><html> <head> <meta charset='UTF-8'> <title></title> <script> var
  • blog 最小生成树Kruskal-数据结构

    最小生成树其应用         什么是最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用krus
  • blog -特别数的

    描述:思路:遍历1-n个数,判断是否满足条件。代码:package club.test;public class TestMain11 { public static void main(String[] args) { int nu
  • blog 数据结构-图的着色

    数据结构-图的着色描述: 图的m-着色判定——给定无向连通图Gm种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色使G中任意相邻的2个顶点着不同颜色?个人感觉图的着色类似与八皇后
  • blog 温故01背包

    01背包是动态规划的一个经典例目: 在n种物品中选取若干件(每种物品只有一件只能选择一次) 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n], 与之相对应
  • blog 栈的应用-迷宫

    1.描述::上面有一个迷宫,灰色部分代表不能通过,白色部分代表可以通过,现在从a点出发,能否找到一条路径到达b点,如果能,输出此路径。下面采用试探解,采用栈结构保存每一步的内容(包括坐标方向),每前进一步都进行四个方向的试探,
  • blog 数据结构-判断单链表是否有环 环的入口地址(java)

    :如上图的一个链表,如何判断一个链表中是否存在环,以及如何出环的入口以及何如出链表的长度。 方案一:利用hash表         首先准备一个hash表如hashMap等,然后从链表头部
  • blog 八皇后

    八皇后,是一个古老而著名的,是回溯的典型案例。该是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,有多少种摆。1.方