[위로][LeetCode]1.Two Sum 문제 풀이 보고서
3990 단어 LeetCodearrayhash-tableTwo-Sum
Subject
출처:https://leetcode.com/problems/two-sum/
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Explain
이 문 제 는 int 형 배열 과 target 수 치 를 지정 합 니 다.배열 의 두 아래 표 시 된 숫자 와 target 을 찾 아야 합 니 다.
아래 표 시 된 두 개의 배열 을 되 돌려 줍 니 다.
Solution
solution 1
가장 멍청 한 방법 은 순환 삽입 이다.
public static int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
if (nums == null || nums.length == 0) {
return result;
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}이 방법 은 시간 복잡 도가 비교적 높 고 O(n)²)。 공간 복잡 도 는 O(1)이다.
solution 2
방법 은 테스트 를 통과 하 자마자 시간 복잡 도가 높 았 다.그리고 이 문제 의 제시 라벨 이[Array][Hash Table]인 것 을 보고 HashMap 을 사용 하여 아래 표 와 값 을 저장 하고 싶 습 니 다.
/** * HashMap <br /> * * @param nums * @param target * @return */
public static int[] twoSum2(int[] nums, int target) {
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
if (i > map.get(target - nums[i])) {
result[0] = map.get(target - nums[i]);
result[1] = i;
} else {
result[0] = i;
result[1] = map.get(target - nums[i]);
}
} else {
map.put(nums[i], i);
}
}
return result;
}nums[i]를 key 로 하고 아래 표 시 된 i 를 value 로 합 니 다.맵 에 target-nums[i]라 는 키 가 있 는 지 판단 합 니 다.
bingo~~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
