FilesExpand file tree

master

/

test31.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (71 loc) · 2.16 KB

master

/

test31.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (71 loc) · 2.16 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

package byteDance;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

/**

* Created by lizeyang on 2020/5/15.

* 递增数组，找出和为k的数对

*/

public class test31 {

//双指针，时间复杂度O(n)

public static int[][] test(int[] nums, int target) {

if (nums == null || nums.length == 0) {

return new int[][]{};

}

List<int[]> list = new ArrayList<>();

int l = 0, r = nums.length - 1;

while (l < r) {

if (nums[l] + nums[r] == target) {

int[] res = new int[2];

res[0] = nums[l];

res[1] = nums[r];

list.add(res);

l++;

r--;

} else if (nums[l] + nums[r] < target) {

l++;

} else {

r--;

}

}

int[][] res = new int[list.size()][];

for (int i = 0; i < list.size(); i++) {

res[i] = list.get(i);

}

return res;

}

//升级：和为k的子数组，如nuns = {1,1,1},k=2;输出[1,1][1,1]

//利用sum-k这样的查补方式找到map里面对应sum-k的value值

public static int subArraySum(int[] nums, int k) {

if (nums == null || nums.length == 0) {

return 0;

}

HashMap<Integer, Integer> map = new HashMap<>();

map.put(0, 1);

int sum = 0;

int count = 0;

for (int i = 0; i < nums.length; i++) {

sum += nums[i];

if (map.containsKey(sum - k)) {

count += map.get(sum - k);

}

if (!map.containsKey(sum)) {

map.put(sum, 1);

} else {

map.put(sum, map.get(sum) + 1);

}

}

return count;

}

public static void main(String[] args) {

int[] nums = {1, 2, 4, 6, 7, 8};

int[][] res = test(nums, 9);

for (int i = 0; i < res.length; i++) {

for (int j = 0; j < res[0].length; j++) {

System.out.print(res[i][j] + " ");

}

System.out.println();

}

System.out.println(subArraySum(nums, 6));

}

}